 2

# Maximum of minimum for every window size

Difficulty: HARD
Avg. time to solve
45 min
Success Rate
50%

Problem Statement
Suggest Edit

#### 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
``````
##### Sample Input 1:
``````2
4
1 2 3 4
5
3 3 4 2 4
``````
##### Sample Output 1:
``````4 3 2 1
4 3 3 2 2
``````
##### Explanation for sample input 1:
``````Test case 1:
Already explained in the question.

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

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

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

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

Minimums of window size 4 = min(3,3,4,2,4) = 2
Maximum among them is 2
The output array should be [4,3,3,2,2].
``````
##### Sample Input 2:
``````2
5
45 -2 42 5 -11
6
-2 12 -1 1 20 1
``````
##### Sample Output 2:
`````` 45 5 -2 -2 -11
20 1  1 -1 -1 -2
``````   Console