# 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.
```

A Simple Solution is to go through all windows of every size, find maximum of all windows. Below is implementation of this idea.

## C++

 `// A naive method to find maximum of minimum of all windows of ` `// different sizes ` `#include ` `#include ` `using` `namespace` `std; ` ` `  `void` `printMaxOfMin(``int` `arr[], ``int` `n) ` `{ ` `    ``// Consider all windows of different sizes starting ` `    ``// from size 1 ` `    ``for` `(``int` `k=1; k<=n; k++) ` `    ``{ ` `        ``// Initialize max of min for current window size k ` `        ``int` `maxOfMin = INT_MIN; ` ` `  `        ``// Traverse through all windows of current size k ` `        ``for` `(``int` `i = 0; i <= n-k; i++) ` `        ``{ ` `            ``// Find minimum of current window ` `            ``int` `min = arr[i]; ` `            ``for` `(``int` `j = 1; j < k; j++) ` `            ``{ ` `                ``if` `(arr[i+j] < min) ` `                    ``min = arr[i+j]; ` `            ``} ` ` `  `            ``// Update maxOfMin if required ` `            ``if` `(min > maxOfMin) ` `              ``maxOfMin = min; ` `        ``} ` ` `  `        ``// Print max of min for current window size ` `        ``cout << maxOfMin << ``" "``; ` `    ``} ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `    ``int` `arr[] = {10, 20, 30, 50, 10, 70, 30}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]); ` `    ``printMaxOfMin(arr, n); ` `    ``return` `0; ` `} `

## Java

 `// A naive method to find maximum of minimum of all windows of ` `// different sizes ` ` `  `class` `Test ` `{ ` `    ``static` `int` `arr[] = {``10``, ``20``, ``30``, ``50``, ``10``, ``70``, ``30``}; ` `     `  `    ``static` `void` `printMaxOfMin(``int` `n) ` `    ``{ ` `        ``// Consider all windows of different sizes starting ` `        ``// from size 1 ` `        ``for` `(``int` `k=``1``; k<=n; k++) ` `        ``{ ` `            ``// Initialize max of min for current window size k ` `            ``int` `maxOfMin = Integer.MIN_VALUE; ` `      `  `            ``// Traverse through all windows of current size k ` `            ``for` `(``int` `i = ``0``; i <= n-k; i++) ` `            ``{ ` `                ``// Find minimum of current window ` `                ``int` `min = arr[i]; ` `                ``for` `(``int` `j = ``1``; j < k; j++) ` `                ``{ ` `                    ``if` `(arr[i+j] < min) ` `                        ``min = arr[i+j]; ` `                ``} ` `      `  `                ``// Update maxOfMin if required ` `                ``if` `(min > maxOfMin) ` `                  ``maxOfMin = min; ` `            ``} ` `      `  `            ``// Print max of min for current window size ` `            ``System.out.print(maxOfMin + ``" "``); ` `        ``} ` `    ``} ` `     `  `    ``// Driver method ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``printMaxOfMin(arr.length); ` `    ``} ` `} `

## Python3

 `# A naive method to find maximum of  ` `# minimum of all windows of different sizes  ` `INT_MIN ``=` `-``1000000` `def` `printMaxOfMin(arr, n):  ` `     `  `    ``# Consider all windows of different  ` `    ``# sizes starting from size 1  ` `    ``for` `k ``in` `range``(``1``, n ``+` `1``):  ` `         `  `        ``# Initialize max of min for ` `        ``# current window size k  ` `        ``maxOfMin ``=` `INT_MIN;  ` ` `  `        ``# Traverse through all windows  ` `        ``# of current size k  ` `        ``for` `i ``in` `range``(n ``-` `k ``+` `1``):  ` `             `  `            ``# Find minimum of current window  ` `            ``min` `=` `arr[i]  ` `            ``for` `j ``in` `range``(k):  ` `                ``if` `(arr[i ``+` `j] < ``min``):  ` `                    ``min` `=` `arr[i ``+` `j] ` ` `  `            ``# Update maxOfMin if required  ` `            ``if` `(``min` `> maxOfMin):  ` `                ``maxOfMin ``=` `min` `                 `  `        ``# Print max of min for current window size  ` `        ``print``(maxOfMin, end ``=` `" "``) ` ` `  `# Driver Code ` `arr ``=` `[``10``, ``20``, ``30``, ``50``, ``10``, ``70``, ``30``]  ` `n ``=` `len``(arr) ` `printMaxOfMin(arr, n) ` ` `  `# This code is contributed by sahilshelangia `

/div>

## C#

 `// C# program using Naive approach to find  ` `// maximum of minimum of all windows of ` `// different sizes ` `using` `System; ` ` `  `class` `GFG{ ` `     `  `    ``static` `int` `[]arr = {10, 20, 30, 50, 10, 70, 30}; ` `     `  `    ``// Function to print maximum of minimum ` `    ``static` `void` `printMaxOfMin(``int` `n) ` `    ``{ ` `         `  `        ``// Consider all windows of different  ` `        ``// sizes starting from size 1 ` `        ``for` `(``int` `k = 1; k <= n; k++) ` `        ``{ ` `             `  `            ``// Initialize max of min for  ` `            ``// current window size k ` `            ``int` `maxOfMin = ``int``.MinValue; ` `     `  `            ``// Traverse through all windows ` `            ``// of current size k ` `            ``for` `(``int` `i = 0; i <= n - k; i++) ` `            ``{ ` `                 `  `                ``// Find minimum of current window ` `                ``int` `min = arr[i]; ` `                ``for` `(``int` `j = 1; j < k; j++) ` `                ``{ ` `                    ``if` `(arr[i + j] < min) ` `                        ``min = arr[i + j]; ` `                ``} ` `     `  `                ``// Update maxOfMin if required ` `                ``if` `(min > maxOfMin) ` `                    ``maxOfMin = min; ` `            ``} ` `     `  `            ``// Print max of min for current window size ` `            ``Console.Write(maxOfMin + ``" "``); ` `        ``} ` `    ``} ` `     `  `    ``// Driver Code ` `    ``public` `static` `void` `Main()  ` `    ``{ ` `        ``printMaxOfMin(arr.Length); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007. `

## PHP

 ` ``\$maxOfMin``) ` `            ``\$maxOfMin` `= ``\$min``; ` `        ``} ` ` `  `        ``// Print max of min for  ` `        ``// current window size ` `        ``echo` `\$maxOfMin` `, ``" "``; ` `    ``} ` `} ` ` `  `    ``// Driver Code ` `    ``\$arr``= ``array``(10, 20, 30, 50, 10, 70, 30); ` `    ``\$n` `= sizeof(``\$arr``); ` `    ``printMaxOfMin(``\$arr``, ``\$n``); ` ` `  `// This code is contributed by nitin mittal. ` `?> `

Output:

`70 30 20 10 10 10 10`

Time complexity of above solution can be upper bounded by O(n3).

We can solve this problem in O(n) time using an Efficient Solution. The idea is to use extra space. Below are detailed steps.
Step 1: Find indexes of next smaller and previous smaller for every element. Next smaller is the nearest smallest element on right side of arr[i]. Similarly, previous smaller element is the nearest smallest element on left side of arr[i].
If there is no smaller element on right side, then next smaller is n.If there is no smaller on left side, then previous smaller is -1.

For input {10, 20, 30, 50, 10, 70, 30}, array of indexes of next smaller is {7, 4, 4, 4, 7, 6, 7}.
For input {10, 20, 30, 50, 10, 70, 30}, array of indexes of previous smaller is {-1, 0, 1, 2, -1, 4, 4}

This step can be done in O(n) time using the approach discussed in next greater element.

Step 2: 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.

Create an auxiliary array ans[n+1] to store the result. Values in ans[] can be filled by iterating through right[] and left[]

```    for (int i=0; i < n; i++)
{
// length of the interval
int len = right[i] - left[i] - 1;

// a[i] is the possible answer for
// this length len interval
ans[len] = max(ans[len], arr[i]);
}```

We get the ans[] array as {0, 70, 30, 20, 0, 0, 0, 10}. Note that ans[0] or answer for length 0 is useless.

Step 3:Some entries in ans[] are 0 and yet to be filled. For example, we know maximum of minimum for lengths 1, 2, 3 and 7 are 70, 30, 20 and 10 respectively, but we don’t know the same for lengths 4, 5 and 6.
Below are few important observations to fill remaining entries
a) Result for length i, i.e. ans[i] would always be greater or same as result for length i+1, i.e., ans[i+1].
b) If ans[i] is not filled it means there is no direct element which is minimum of length i and therefore either the element of length ans[i+1], or ans[i+2], and so on is same as ans[i]
So we fill rest of the entries using below loop.

```    for (int i=n-1; i>=1; i--)
ans[i] = max(ans[i], ans[i+1]);
```

Below is implementation of above algorithm.

## C++

 `// An efficient C++ program to find maximum of all minimums of ` `// windows of different sizes ` `#include ` `#include ` `using` `namespace` `std; ` ` `  `void` `printMaxOfMin(``int` `arr[], ``int` `n) ` `{ ` `    ``stack<``int``> s; ``// Used to find previous and next smaller ` ` `  `    ``// Arrays to store previous and next smaller ` `    ``int` `left[n+1];   ` `    ``int` `right[n+1];  ` ` `  `    ``// Initialize elements of left[] and right[] ` `    ``for` `(``int` `i=0; i= arr[i]) ` `            ``s.pop(); ` ` `  `        ``if` `(!s.empty()) ` `            ``left[i] = s.top(); ` ` `  `        ``s.push(i); ` `    ``} ` ` `  `    ``// Empty the stack as stack is going to be used for right[] ` `    ``while` `(!s.empty()) ` `        ``s.pop(); ` ` `  `    ``// Fill elements of right[] using same logic ` `    ``for` `(``int` `i = n-1 ; i>=0 ; i-- ) ` `    ``{ ` `        ``while` `(!s.empty() && arr[s.top()] >= arr[i]) ` `            ``s.pop(); ` ` `  `        ``if``(!s.empty()) ` `            ``right[i] = s.top(); ` ` `  `        ``s.push(i); ` `    ``} ` ` `  `    ``// Create and initialize answer array ` `    ``int` `ans[n+1]; ` `    ``for` `(``int` `i=0; i<=n; i++) ` `        ``ans[i] = 0; ` ` `  `    ``// Fill answer array by comparing minimums of all ` `    ``// lengths computed using left[] and right[] ` `    ``for` `(``int` `i=0; i=1; i--) ` `        ``ans[i] = max(ans[i], ans[i+1]); ` ` `  `    ``// Print the result ` `    ``for` `(``int` `i=1; i<=n; i++) ` `        ``cout << ans[i] << ``" "``; ` `} ` ` `  `// Driver program ` `int` `main() ` `{ ` `    ``int` `arr[] = {10, 20, 30, 50, 10, 70, 30}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]); ` `    ``printMaxOfMin(arr, n); ` `    ``return` `0; ` `} `

## Java

 `// An efficient Java program to find maximum of all minimums of ` `// windows of different size ` ` `  `import` `java.util.Stack; ` ` `  `class` `Test ` `{ ` `    ``static` `int` `arr[] = {``10``, ``20``, ``30``, ``50``, ``10``, ``70``, ``30``}; ` `     `  `    ``static` `void` `printMaxOfMin(``int` `n) ` `    ``{ ` `        ``// Used to find previous and next smaller ` `        ``Stack s = ``new` `Stack<>(); ` `      `  `        ``// Arrays to store previous and next smaller ` `        ``int` `left[] = ``new` `int``[n+``1``];   ` `        ``int` `right[]  = ``new` `int``[n+``1``];  ` `      `  `        ``// Initialize elements of left[] and right[] ` `        ``for` `(``int` `i=``0``; i= arr[i]) ` `                ``s.pop(); ` `      `  `            ``if` `(!s.empty()) ` `                ``left[i] = s.peek(); ` `      `  `            ``s.push(i); ` `        ``} ` `      `  `        ``// Empty the stack as stack is going to be used for right[] ` `        ``while` `(!s.empty()) ` `            ``s.pop(); ` `      `  `        ``// Fill elements of right[] using same logic ` `        ``for` `(``int` `i = n-``1` `; i>=``0` `; i-- ) ` `        ``{ ` `            ``while` `(!s.empty() && arr[s.peek()] >= arr[i]) ` `                ``s.pop(); ` `      `  `            ``if``(!s.empty()) ` `                ``right[i] = s.peek(); ` `      `  `            ``s.push(i); ` `        ``} ` `      `  `        ``// Create and initialize answer array ` `        ``int` `ans[] = ``new` `int``[n+``1``]; ` `        ``for` `(``int` `i=``0``; i<=n; i++) ` `            ``ans[i] = ``0``; ` `      `  `        ``// Fill answer array by comparing minimums of all ` `        ``// lengths computed using left[] and right[] ` `        ``for` `(``int` `i=``0``; i=``1``; i--) ` `            ``ans[i] = Math.max(ans[i], ans[i+``1``]); ` `      `  `        ``// Print the result ` `        ``for` `(``int` `i=``1``; i<=n; i++) ` `            ``System.out.print(ans[i] + ``" "``); ` `    ``} ` `     `  `    ``// Driver method ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``printMaxOfMin(arr.length); ` `    ``} ` `} `

## Python3

# An efficient Python3 program to find
# maximum of all minimums of windows of
# different sizes

def printMaxOfMin(arr, n):

s = [] # Used to find previous
# and next smaller

# Arrays to store previous and next
# smaller. Initialize elements of
# left[] and right[]
left = [-1] * (n + 1)
right = [n] * (n + 1)

# Fill elements of left[] using logic discussed on
# https:#www.geeksforgeeks.org/next-greater-element
for i in range(n):
while (len(s) != 0 and
arr[s[-1]] >= arr[i]):
s.pop()

if (len(s) != 0):
left[i] = s[-1]

s.append(i)

# Empty the stack as stack is going
# to be used for right[]
while (len(s) != 0):
s.pop()

# Fill elements of right[] using same logic
for i in range(n – 1, -1, -1):
while (len(s) != 0 and arr[s[-1]] >= arr[i]):
s.pop()

if(len(s) != 0):
right[i] = s[-1]

s.append(i)

# Create and initialize answer array
ans = [0] * (n + 1)
for i in range(n + 1):
ans[i] = 0

# Fill answer array by comparing minimums
# of all. Lengths computed using left[]
# and right[]
for i in range(n):

# Length of the interval
Len = right[i] – left[i] – 1

# arr[i] is a possible answer for this
# Length ‘Len’ interval, check if arr[i]
# is more than max for ‘Len’
ans[Len] = max(ans[Len], arr[i])

# Some entries in ans[] may not be filled
# yet. Fill them by taking values from
# right side of ans[]
for i in range(n – 1, 0, -1):
ans[i] = max(ans[i], ans[i + 1])

# Prthe result
for i in range(1, n + 1):
print(ans[i], end = ” “)

# Driver Code
if __name__ == ‘__main__’:

arr = [10, 20, 30, 50, 10, 70, 30]
n = len(arr)
printMaxOfMin(arr, n)

# This code is contributed by PranchalK

## C#

 `// An efficient C# program to find maximum  ` `// of all minimums of windows of different size  ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GFG ` `{ ` `public` `static` `int``[] arr = ``new` `int``[] {10, 20, 30, 50, ` `                                     ``10, 70, 30}; ` ` `  `public` `static` `void` `printMaxOfMin(``int` `n) ` `{ ` `    ``// Used to find previous and next smaller  ` `    ``Stack<``int``> s = ``new` `Stack<``int``>(); ` ` `  `    ``// Arrays to store previous  ` `    ``// and next smaller  ` `    ``int``[] left = ``new` `int``[n + 1]; ` `    ``int``[] right = ``new` `int``[n + 1]; ` ` `  `    ``// Initialize elements of left[]  ` `    ``// and right[]  ` `    ``for` `(``int` `i = 0; i < n; i++) ` `    ``{ ` `        ``left[i] = -1; ` `        ``right[i] = n; ` `    ``} ` ` `  `    ``// Fill elements of left[] using logic discussed on  ` `    ``// https://tutorialspoint.dev/slugresolver/next-greater-element/  ` `    ``for` `(``int` `i = 0; i < n; i++) ` `    ``{ ` `        ``while` `(s.Count > 0 &&  ` `               ``arr[s.Peek()] >= arr[i]) ` `        ``{ ` `            ``s.Pop(); ` `        ``} ` ` `  `        ``if` `(s.Count > 0) ` `        ``{ ` `            ``left[i] = s.Peek(); ` `        ``} ` ` `  `        ``s.Push(i); ` `    ``} ` ` `  `    ``// Empty the stack as stack is going  ` `    ``// to be used for right[]  ` `    ``while` `(s.Count > 0) ` `    ``{ ` `        ``s.Pop(); ` `    ``} ` ` `  `    ``// Fill elements of right[] using ` `    ``// same logic  ` `    ``for` `(``int` `i = n - 1 ; i >= 0 ; i--) ` `    ``{ ` `        ``while` `(s.Count > 0 &&  ` `               ``arr[s.Peek()] >= arr[i]) ` `        ``{ ` `            ``s.Pop(); ` `        ``} ` ` `  `        ``if` `(s.Count > 0) ` `        ``{ ` `            ``right[i] = s.Peek(); ` `        ``} ` ` `  `        ``s.Push(i); ` `    ``} ` ` `  `    ``// Create and initialize answer array  ` `    ``int``[] ans = ``new` `int``[n + 1]; ` `    ``for` `(``int` `i = 0; i <= n; i++) ` `    ``{ ` `        ``ans[i] = 0; ` `    ``} ` ` `  `    ``// Fill answer array by comparing ` `    ``// minimums of all lengths computed  ` `    ``// using left[] and right[]  ` `    ``for` `(``int` `i = 0; i < n; i++) ` `    ``{ ` `        ``// length of the interval  ` `        ``int` `len = right[i] - left[i] - 1; ` ` `  `        ``// arr[i] is a possible answer for  ` `        ``// this length 'len' interval, check x ` `        ``// if arr[i] is more than max for 'len'  ` `        ``ans[len] = Math.Max(ans[len], arr[i]); ` `    ``} ` ` `  `    ``// Some entries in ans[] may not be  ` `    ``// filled yet. Fill them by taking  ` `    ``// values from right side of ans[]  ` `    ``for` `(``int` `i = n - 1; i >= 1; i--) ` `    ``{ ` `        ``ans[i] = Math.Max(ans[i], ans[i + 1]); ` `    ``} ` ` `  `    ``// Print the result  ` `    ``for` `(``int` `i = 1; i <= n; i++) ` `    ``{ ` `        ``Console.Write(ans[i] + ``" "``); ` `    ``} ` `} ` ` `  `// Driver Code  ` `public` `static` `void` `Main(``string``[] args) ` `{ ` `    ``printMaxOfMin(arr.Length); ` `} ` `} ` ` `  `// This code is contributed by Shrikant13 `

Output:

`70 30 20 10 10 10 10`

Time Complexity: O(n)
Auxiliary Space: O(n)