Problem of the day
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].
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.
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’.
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
2
4
1 2 3 4
5
3 3 4 2 4
4 3 2 1
4 3 3 2 2
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].
2
5
45 -2 42 5 -11
6
-2 12 -1 1 20 1
45 5 -2 -2 -11
20 1 1 -1 -1 -2