Maximum of minimum for every window size

PROBLEM STATEMENT

You are given an array of ‘N’ integers, you need to find the maximum of minimum for every window size. The size of the window should vary from 1 to ‘N’ only.

For example:

ARR = [1,2,3,4]
Minimums of window size 1 = min(1), min(2), min(3), min(4) = 1,2,3,4
Maximum among (1,2,3,4)  is 4

Minimums of window size 2 = min(1,2), min(2,3),   min(3,4) = 1,2,3
Maximum among (1,2,3) is 3

Minimums of window size 3 = min(1,2,3), min(2,3,4) = 1,2
Maximum among (1,2) is 2

Minimums of window size 4 = min(1,2,3,4) = 1
Maximum among them is 1
The output array should be [4,3,2,1].

Input Format:

The first line of the input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single positive integer ‘N’ denoting the number of the elements present in the array.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array.

Output Format:

The only line of output of each test case should contain ‘N’ space-separated integer such that he ith integer indicates the maximum of minimums of the windows of size ‘i’.

Constraints:

1 <= T <= 100
1 <= N <= 10 ^ 4 
-10 ^ 9 <= ARR[i] <= 10 ^ 9

Where ‘T’ is the number of test cases, ‘N’ is the size of the array and ‘ARR[i]’ is the size of the array elements.

Time Limit: 1 sec

Approach 1

We will use two nested loops for sliding on the window of every possible size and one more inner loop to traverse on the window and store the minimum element of the current window in a ‘temp’ variable.
We will create an array named ‘answer’. The ‘answer[i]’ will store the maximum of all the available minimum of every window size ‘i’.
If ‘i’ and ‘j’ are the starting and ending indexes of the window then its length = j-i+1.
So we update our ‘answer[length]’ with the maximum of all the available minimum of every window size ‘i’ with the help of a ‘temp’ variable
i.e, ‘answer[length]’ = max( answer[length] , temp ).

Try Problem

Approach 2

We will follow some reverse strategy for building our final solution instead of finding minimums for every possible window. We will find how many windows our current element can be the answer.
To find that we will calculate the indexes of the next smaller and previous smaller element for every element given in the array. The next smaller element is some number that is smaller than the current element and lies nearest on the right-hand side of the current element. Similarly, the previous smaller is some number that is smaller than the current element and lies nearest on the left-hand side of the current element.
If there is no next smaller element for the current number then we will assume its index having value N and if there is no previous smaller element for the current number then we will assume its index having value -1.
The above two arrays of the next smaller and previous smaller can be done in linear time with the help of Monotonic Stack.
Suppose ‘next[i]’ = index of next smaller element, ‘prev[i]’ = index of previous smaller element. Now, we know the ‘ARR[i]’ will be the minimum of the window of size -> size = next[i] - prev[i] + 1. So, we will directly use the value of ‘ARR[i]’ for updating the answer of window having size = next[i] - prev[i] + 1.
After doing this for every element we can update our answer for windows of some different lengths i.e, we are still left with some window sizes for which the answer is not calculated yet. So to fill the remaining entries we will use some observations listed below:-
- The answer for some window having size ‘L’ would always be greater than or equal to the answer for a window having a length greater than L i.e, L+1, L+2 .... so on.
- Hence, we will update the remaining uncalculated answer for some windows having length ‘L’ with the maximum suffix starting from length ‘L+1’.