Please explain the solution in detail using examples as this question bounced off even after seeing the gfg editorial

#1

Find maximum of minimum for every window size in a given array
Given an integer array of size n, find the maximum of the minimum’s of every window size in the array. Note that window size varies from 1 to n.
Example:

Input: arr[] = {10, 20, 30, 50, 10, 70, 30}
Output: 70, 30, 20, 10, 10, 10, 10

First element in output indicates maximum of minimums of all
windows of size 1.
Minimums of windows of size 1 are {10}, {20}, {30}, {50}, {10},
{70} and {30}. Maximum of these minimums is 70

Second element in output indicates maximum of minimums of all
windows of size 2.
Minimums of windows of size 2 are {10}, {20}, {30}, {10}, {10},
and {30}. Maximum of these minimums is 30

Third element in output indicates maximum of minimums of all
windows of size 3.
Minimums of windows of size 3 are {10}, {20}, {10}, {10} and {10}.
Maximum of these minimums is 20

Similarly other elements of output are computed.

#2

@affanahmed,

Break this question into 2 parts. See, first we have to find the minimum element in window of variable sizes and after that we need to find the maximum of these elements (the elements here are minimum elements in each window) .

Input: arr[] = {10, 20, 30, 50, 10, 70, 30} this is array given to us. Now let us say that the window size (given by k is 3).

Windows to be analyzed will be:
10,20,30 -> minimum from this window will be 10
20,30,50 -> min from this window will be 20
30,50,10 -> min from this window will be 10
50,10,70 -> min from this window will be 10
10,70,30 -> min from this window will be 10

Now the final answer is maximum of {10,20,10,10,10}, hence it will be 20.

Now the naive solution has complexity of O(n^3). But if we use stack we can do it in O(n).

First find out the next smaller element for every element. In case the element is the smallest element in the array put ‘n’ (number of elements) otherwise put the index.
For input {10, 20, 30, 50, 10, 70, 30}, array of indexes of next smaller is {7, 4, 4, 4, 7, 6, 7}, say this is right array.

Now we find the previous smaller element for every element. In case their is no smallest element on the left side we put -1.
For input {10, 20, 30, 50, 10, 70, 30}, array of indexes of previous smaller is {-1, 0, 1, 2, -1, 4, 4}, say this is left array.

Once we have indexes of next and previous smaller, we know that arr[i] is a minimum of a window of length “right[i] – left[i] – 1”. Lengths of windows for which the elements are minimum are {7, 3, 2, 1, 7, 1, 2}. This array indicates, first element is minimum in window of size 7, second element is minimum in window of size 3, and so on.
After that just store the answer in a array and return ut.

#3

How you came up with the approach and can all the questions like this can be solved by your approach?

#4

@affanahmed,
Its mostly about practice to get an intuition. Also, we have a similar question in that you have to find the max element in a given array and window size is given. That question is very similar to this, so you can practice that as well. Apart from that, you can use codeforces, codechef for practice as well.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.