Find the Maximum of Minimum for Every Window Size in a Given Array

In this tutorial, we are going to find the maximum and minimum for every window size in a given Array using C++, Java, and Python programming languages.

Problem Statement

We have an array of integers of size ‘n,’ and we need to print the maximum of minimums of every valid window size in the array where the window size ranges from 1 to n.

Example

Input - arr[ ] = {15, 20, 8, 30, 12, 20}
Output - 30, 15, 12, 8, 8, 8

Explanation:

1. The first element (30) of output is the maximum of minimums of all windows of size 1.
2. Windows of size 1 are - {15}, {20}, {8}, {30}, {12}, {20} out of which maximum is 30.
3. The second element in output represents the maximum of minimums of all windows of size 2.
4. Windows of size 2 are - {15,20}, {20,8}, {8,30}, {30,12}, {12,20}. Their minimum are 15, 8, 8, 12, and 12, respectively, and their maximum is 15.
5. The third element in output represents the maximum of minimums of all windows of size 3. Minimums of windows of size 3 are {8}, {8}, {8}, and {12}, and their maximum is 12.
6. Using the same idea, other elements can be calculated.

How to Find the Maximum and Minimum for Every Window Size in a Given Array?

1) Brute Force - A Simple Approach to Find the Maximum and Minimum for Every Window Size in a Given Array

The brute force approach is to generate and check for all windows of size ‘x’ where x ranges from 1 to n. Then, we need to find the minimum element of all windows for a particular value of x and store the maximum of those minimums.

To generate all windows, we need to know about starting and endpoints of windows that can be done easily by two nested loops, and for checking for windows of all sizes from 1 to n, we need another nested loop.

Ultimately, we have to use three nested loops for the window size, starting point, and endpoint. The implementation of the approach discussed above is as follows:

C++ Programming

#include <bits/stdc++.h>
using namespace std;
void printMaxofMinForEveryWindow(int arr[],int n){
    // Checking for windows of all valid sizes i.e. from 1 to n
    for(int windowSize=1;windowSize<=n;windowSize++)
    {
        // Initializing maximum with minimum possible value
        int maximum=INT_MIN;
        
        // Traversing through all windows of current windowSize
        for(int i=0;i<=n-windowSize;i++)
        {
            // Checking for minimum element in current window
            int minimum=arr[i];
            for(int j=1;j<windowSize;j++)
            {
                minimum=min(minimum,arr[i+j]);
            }
            // Updating value of max if the minimum of this window is greater than max. 
            maximum=max(maximum,minimum);
        }
        // Print max of min for all window of current windowSize
        cout<<maximum<<" ";
    }
}
int main() {
	int arr[]={15, 20, 8, 30, 12, 20};
	int n = sizeof(arr)/sizeof(arr[0]);
	printMaxofMinForEveryWindow(arr,n);
	cout<<endl;
	return 0;
}

Output

Java Programming

import java.util.*;
public class Main {
    public static void printMaxofMinForEveryWindow(int arr[],int n){
        // Checking for windows of all valid sizes i.e. from 1 to n
        for(int windowSize=1;windowSize<=n;windowSize++)
        {
            // Initializing max with minimum possible value
            int max=Integer.MIN_VALUE;
            
            // Traversing through all windows of current windowSize
            for(int i=0;i<=n-windowSize;i++)
            {
                // Checking for minimum element in current window
                int min=arr[i];
                for(int j=1;j<windowSize;j++)
                {
                    min=Math.min(min,arr[i+j]);
                }
                // Updating value of max if the minimum of this window is greater than max. 
                max=Math.max(max,min);
            }
            // Print max of min for all window of current windowSize
            System.out.print(max+" ");
        }
    }
  public static void main (String[] args) {
      
    int arr[]={15, 20, 8, 30, 12, 20};
    
    printMaxofMinForEveryWindow(arr,arr.length);
    System.out.println();
  }
}

Output

Python Programming

INT_MIN = -9999999
def printMaxofMinForEveryWindow(arr, n):
     
    #Checking for windows of 
    #all valid sizes i.e. from 1 to n
    for windowSize in range(1, n + 1):
         
        # Initializing maxOfMin 
        # with very small value
        maxOfMin = INT_MIN;
 
        # Traversing through all 
        # windows of current windowSize
        for i in range(n - windowSize + 1):
             
            # Checking for minimum element in current window
            min = arr[i]
            for j in range(windowSize):
                if (arr[i + j] < min): min = arr[i + j] # Updating value of max if minimum # of this window is greater than max. if (min > maxOfMin):
                maxOfMin = min
                 
        # Print max of min for all window of current windowSize
        print(maxOfMin, end = " ")
 
arr = [15, 20, 8, 30, 12, 20]
n = len(arr)
printMaxofMinForEveryWindow(arr, n)

Output :

30 15 12 8 8 8

Complexity Analysis

• Time Complexity: O(n^3) since we have used three nested loops in the approach.
• Extra Space : O(1) because we are using variables only for storing starting and endpoints of the windows.

2) An Efficient Approach to Find the Maximum and Minimum for Every Window Size in a Given Array

For each element, we can find what is the maximum size of the window in which that element is minimum and that too in linear time complexity . We use this idea to build our algorithm.

Algorithm

Step 1

For each element, find the index of the first smaller element on the right side (next smaller element) and on the left side (previous smaller element). If there is no element on the left side that is smaller than a[i], then the previous smaller element will be -1, and if there is no element on the right side that is smaller than a[i], then the next smaller element will be n.

For input {15, 20, 8, 30, 12, 20}, the array of indexes of the previous smaller elements are {-1, 0, -1, 2, 2, 4}. For the input {15, 20, 8, 30, 12, 20}, the array of indexes next smaller elements are {2, 2, 6, 4, 6, 6}.

Step 2

Now that we have indexes of the next smaller and previous smaller elements, by observation, we can determine the length of the window in which a[i] is minimum, and that would be “ right[i] - left[i] - 1. ”

Using the same approach, we can find that the length of windows for which a[i] is minimum can be represented by the array {2, 1, 6, 1, 3, 1}. This means that the first element is minimum for a window size of 2, second for a window size of 1, and so on.

Now, we can create an auxiliary answer array of size n+1, ans[n+1] and fill the values according to values of left[] and right[].  for (int i=0; i < n; i++)     {         // length of the interval for which a[i] is minimum         int length = right[i] - left[i] - 1;         // arr[i] may be a possible answer for this length interval,         // so we store the maximum possible answer.

ans[length] = max(ans[length], arr[i]);     }: Using this we get the ans[] array as {0, 30, 15, 12, 0, 0, 8}.

Here, ans[0] represents the maximum of the minimum of the window of size 0, which is not required.

Step 3

We can see that some elements in the answer array are 0, which means that they are yet to be filled. In the above case, we do not know the maximum of minimums of windows of lengths 4 and 5. We can make two observations here:

1. 1. Answers for the window of length i, i.e., ans[i] would always be greater or equal to the result for the window of length i+1, i.e., ans[i+1].
   2. If ans[i] is not filled (means if it 0), it means there is no single element which is minimum of the window of length i and therefore either the element of length ans[i+1], or ans[i+2], and so on would be the answer to ans[i]. So we fill the remaining of the entries using the given for loop: for (int i=n-1; i>=1; i--) ans[i] = max(ans[i+1], ans[i]);

Below is the implementation of the above algorithm.

C++ Programming

#include <bits/stdc++.h>
using namespace std;

void printMaxofMinForEveryWindow(int arr[],int n){
    
    // Creating left and right array of size n,
    // And initializing with -1 and n respectively. 
    int left[n];
    int right[n];
    for(int i=0;i<n;i++)
    {
        left[i]=-1;
        right[i]=n;
    }
    // Fill the left array.
    stack st;
    for(int i=0;i<n;i++) { while(!st.empty()&&arr[st.top()]>=arr[i])
         st.pop();
         if(st.empty()) left[i]=-1;
         else left[i]=st.top();
         
        st.push(i);
    }
    // Clear the array 
    while(!st.empty()) st.pop();
    
    // Fill the right array.
    for(int i=n-1;i>-1;i--)
    {
         while(!st.empty()&&arr[st.top()]>=arr[i])
         st.pop();
         if(st.empty()) right[i]=n;
         else right[i]=st.top();
         
        st.push(i);
    }
    
    //Creating answer array of size n+1 for all windows
    //ranging from 0 to n-1 of which 0 size window is of no use
    // and initializing with 0.
    int ans[n+1];
    
    for(int i=0;i<=n;i++) 
    ans[i]=0;
    
    for(int i=0;i<n;i++) { // Finding length of window in which arr[i] is the minimum possible element. int length=right[i]-left[i]-1; // arr[i] is a possible answer for this length 'length' interval, //check if arr[i] is more than max for 'length' if(arr[i]>ans[length]) ans[length]=arr[i];
    }
    // Fill the values which are not 
    //filled yet by checking values on the right side of the array.
    for(int i=n-1;i>0;i--)
    {
        ans[i]=max(ans[i],ans[i+1]);
    }
    //Printing max of min for all window sizes from 1 to n.
    for(int i=1;i<=n;i++)
    cout<<ans[i]<<" ";
}
int main() {
  int arr[]={15, 20, 8, 30, 12, 20};
  int n = sizeof(arr)/sizeof(arr[0]);
  printMaxofMinForEveryWindow(arr,n);
  cout<<endl;
  return 0;
}

Output:

Java Programming

import java.util.*;
public class Main {
     public static int[] prevSmaller(int[] a) {
         
         // Finding the index of the first smaller element on the left side, using Stacks. 
 
        int n=a.length;
        int ans[]=new int[n];
        Stack st=new Stack<>();
        for(int i=0;i<n;i++) { while(!st.isEmpty()&&a[st.peek()]>=a[i])
             st.pop();
             if(st.isEmpty()) ans[i]=-1;
             else ans[i]=st.peek();
             
            st.push(i);
        }
        return ans;
    }
     public static int[] nextSmaller(int[] a) {
         // Finding index of first smaller element on right side, using Stacks. 
   
        int n=a.length;
        int ans[]=new int[n];
        Stack st=new Stack<>();
        for(int i=n-1;i>-1;i--)
        {
             while(!st.isEmpty()&&a[st.peek()]>=a[i])
             st.pop();
             if(st.isEmpty()) ans[i]=n;
             else ans[i]=st.peek();
             
            st.push(i);
        }
        return ans;
    }
    public static void printMaxofMinForEveryWindow(int arr[],int n){
        
        //Finding index of first smaller element on left side.
        int left[]=prevSmaller(arr);
        //Finding index of first smaller element on left side.
        int right[]=nextSmaller(arr);
        
        //Creating answer array of size n+1 for all windows
        //ranging from 0 to n-1 of which 0 size window is of no use.
        int ans[]=new int[n+1];
        for(int i=0;i<n;i++) { // Finding length of window in which //arr[i] is the minimum possible element. int length=right[i]-left[i]-1; // arr[i] is a possible answer for this length 'length' //interval, check if arr[i] is more than max for 'length' if(arr[i]>ans[length]) ans[length]=arr[i];
        }
        
        // Fill the values which are not filled
        //yet by checking values on the right side of the array.
        for(int i=n-1;i>0;i--)
        {
            ans[i]=Math.max(ans[i],ans[i+1]);
        }
        //Printing max of min for all window sizes from 1 to n.
        for(int i=1;i<=n;i++)
        System.out.print(ans[i]+" ");
    }
    public static void main (String[] args) {
        int arr[]={15, 20, 8, 30, 12, 20};
        
        printMaxofMinForEveryWindow(arr,arr.length);
        System.out.println();
    }
}

Output:

Python Programming

def printMaxofMinForEveryWindow(arr, n):
     
    s = [] # Used to find previous
        # and next smaller
 
    # Create left and right array
    # to store previous and next smaller
    # element, initialize with -1 and n respectively.
    left = [-1] * (n + 1)
    right = [n] * (n + 1)
 
    # Fill elements of left[]
    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)
 
    # Clear the stack
    # to use it again for
    # filling the right array.
    while (len(s) != 0):
        s.pop()
 
    # Fill elements of right[] using the same approach
    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
    # of size n+1.
    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):
         
        # Finding length of window in which
        # arr[i] is the minimum possible element.
        Length = right[i] - left[i] - 1
 
        # arr[i] is a possible answer for this
        # length 'Length' interval,check if arr[i]
        # is more than max for 'Length'
        ans[Length] = max(ans[Length], arr[i])
 
    # Fill the values which are not
    # filled yet by checking values
    # on the right side of the array.
    for i in range(n - 1, 0, -1):
        ans[i] = max(ans[i], ans[i + 1])
 
    # Print the result
    for i in range(1, n + 1):
        print(ans[i], end = " ")
 
# Driver Code
if __name__ == '__main__':
 
    arr = [15, 20, 8, 30, 12, 20]
    n = len(arr)
    printMaxofMinForEveryWindow(arr, n)
    print()

Output :

30 15 12 8 8 8

Complexity Analysis

• Time Complexity: O(n). Finding the next smaller element and the previous smaller element takes linear time.
• Extra Space: O(n). We have used a stack for calculating next and previous smaller arrays to store the intermediate results.

Wrapping Up!

In this blog post, we learned how to calculate the maximum of minimums for every possible window of valid size. We discussed two approaches in which we can solve this problem. This article also contains well-explained codes of both the approaches in the three most popular languages, namely C++, Java, and Python, along with their respective outputs for a better understanding.

We sincerely hope that this article has walked you through in-depth and important concepts of arrays and stacks and you have learned how to approach such kinds of problems. We hope that you will now be able to solve this problem as well as its other variations seamlessly and efficiently.

Happy Coding!

People are also reading:

• WAP to Print Triangle Using * Character
• Find ancestors of a given node in a Binary Tree
• Circular Linked List
• Subset Sum Problem
• Clone a Singly Linked List
• Linked List
• Maximum size square sub-matrices with all 1’s
• Merge Sort for Linked Lists
• Tree vs Graph
• Algorithms Basics