Some Important Searching and Sorting Related Problems with Hints

 1. Sliding Window Maximum, Difficulty: Hard

First Read the problem statement. In this problem, we have given a window that size is 'K', every time we have to move this window from left to right and pick the largest number from the window.

Suppose, our given array is A = {1,3,-1,-3,5,3,6,7} and Window size, K = 3

The window moving look like this,

       Window position            Max

[1  3  -1] -3  5  3  6  7           3

 1 [3  -1  -3] 5  3  6  7           3

 1  3 [-1  -3  5] 3  6  7           5

 1  3  -1 [-3  5  3] 6  7           5

 1  3  -1  -3 [5  3  6] 7           6

 1  3  -1  -3  5 [3  6  7]          7

SO, the ans is, {3,3,5,5,6,7}
First, see we can't solve this problem using Bruteforce {1<=Array size<=10^5} method, we need to optimize this.

Before solving the problem, think that we already know the first largest value of the first window, Now how can we get the 2nd window largest, and so on.

If we have a Container that can find the largest value at the same time we can remove the first value of the current window and insert the last value of the next window then the problem will be solved.

Container? is it Multiset? Priority queue? Think.

2. Towers, Difficulty: Easy

Read the problem statement, we have given an array of integers. We have to build some towers in the order of the given array.

How the tower of numbers look like? the first element is maximum, then the second element is less than the previous element, and so on.

Obviously, we cant solve this problem using the brute force method.
Again for solving this problem, we need a container that can give the information of the existence of exactly greater value than the current value at the same time it can erase any number.

3. Josephus Problem I, Difficulty: Easy

Very famous problem. Given n peoples, currently, they are in a circle.
Every time we have to remove the 2nd person. Initially, counting starts from 1.

The First observation of solving this problem is we have to consider every time that current child-size is odd or even, then simply we can pass the alive list to the current child list.

4. Room Allocation - Medium

This Problem is really easy to understand. You have given N person's Comming and Leaving time. You have to calculate how many rooms can be used and which person can be used in which room(room id).

For solving this problem, we have to maintain their id, current entry time, current leaving time, and most important we have to sort them by their entry time. At the same time, we have to handle the last person leaving time so that we can compare it with the current person's entry time so that the current person can use the previous person's room or not.

Solvable with Nlog(N) complexity.
Better understanding see my code.

Some Basic STL Operation

Upper Bound & Lower Bound:
Suppose we are searching for a value that is exactly greater than value 'x', or let's say we are searching for a value that is exactly greater or equal to value 'x'.

Let me more explain, suppose we have a vector.
vector<int>a = {1,2,4,7,9}, sorted in ascending order.

Now, we are searching for a value in vector 'a' that is exactly greater than '3'. So if start searching for the left to right we can get '4' in the 2nd(0th indexed) position. 

This searching for exactly greater value is called Upper_bound. This means the upper value of 'x'.
auto position = upper_bound(a.begin(), a.end(), x) - a.begin(); that's return the position of greater value(if exits in vector)

Similarly, searching for exactly greater or equal(>=) value is called Lower_bound.
auto position = lower_bound(a.begin(), a.end(), x) - a.begin(); 
that will also return the positon.

Examples,

The lower bound of 3 is the index 1.
The upper bound of 3 is the index 2.

In this case, it is logarithmic complexity. If we search for a random value, we can do a[x], this we take O(1).

Set and Multiset:

Set and Multiset are the very useful STL techniques that have been used in most algorithmic problems.

Set contains only unique elements. Multiset contains duplicates value.
Suppose we insert this(2,1,2,2,4,5,9,1) values into Set and Multiset,

Set :      (1, 2, 4, 5, 9)
Multiset: (1, 1, 2, 2, 2, 4, 5, 9)

One thing didn't mention yet before that is, both of them contain values sorted in ascending order.

Now, if we apply upper bound and lower bound in Set and Multiset, this will not work as before.

Set and Multiset has lower_bound and upper bound.
Simply we can do, s.upper_bound('x'),(set or multiset in both case)

Here it is log N complexity, but if we want random access like s[n], it's not possible because set and multiset don't have random access.

we can also do, erase and count operations in set and multiset.

Example:

Set,
(2,7,5,5) => set s(2,5,7) [ after inserting into set ]
s.erase(5) => s(2,7)

Multiset,

(2,7,5,5) => multiset m(2,5,5,7)
m.erase(5) => it will remove all '5' from multiset.
if we want to remove only one '5' form there, we have to do remove one's position.

auto it = m.lower_bound(5) => 1
m.erase(it) => m(2,5,7)


Stack:

Stack is one of the data structures and supports two types of operations.
It maintains the LIFO sequence, which means Last-In-First-Out.

Picture from internet

We can use "A pile of plates" as an example. Here if we add a plate that will take place on the top, after that if we want to remove any plate, the latest one will be removed.

Two types of operation:
Push: Add an element to the end of the stack.

Pop: Remove an element from the top of the stack.

Details with example:

stack<int> st;

st.push(2); st.push(3); st.push(5); st.push(8);

// stack now is [2, 3, 5, 8]    

int topElement = st.top();

cout << topElement << endl; // 8

st.pop();  // stack now is [2, 3, 5]

st.pop(); // stack now is [2, 3]

Queue:

The queue is a container, it maintains the FIFO sequence, which means First-In-First-Out.

Source: Internet

We can take "People's Line" as an example of a queue, where a bunch of people makes lines for tickets, food, or something else.
In the line, First people come first then the second person, and so on. Declare as, queue<data_types>Q;

Some most used operations of Queue,

Q.empty()
Q.size()
Q.front()
Q.back()
Q.push() [ push_back ]
Q.pop()   [ pop_front ]

Usually takes O(1) complexity.


Priority Queue:

Another data structure supports some very important operations.

Insert an element in the queue in O(logN) time (N size of the queue).
Find the largest (or the smallest) element in the queue in O(1) time.
Remove an element from the queue in O(logN) time.

priority_queue<int> q; // Greater Value first, we can also put (-ve) value

q.push(2);q.push(3);q.push(8);

// q.top() finds the maximum element in the queue.

cout << q.top() << endl; // prints 8

q.pop(); // q.pop() removes the maximum element from the queue.

cout << q.top() << endl; // prints 3 now.

q.push(15);

cout << q.top() << endl; // prints 15

priority_queue<int, vector<int>, greater<int>> q; // Small value first

        

q.push(2);q.push(3);q.push(8);

// q.top() now finds the minimum element in the queue.

cout << q.top() << endl; // prints 2

q.pop(); // q.pop() also removes the minimum element now.

cout << q.top() << endl; // prints 3 now.

q.push(15);

cout << q.top() << endl; // prints 3

Related Problems:
Concert Ticket - CSES
Valid Parentheses(Leetcode)