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

Difficulty Level Medium
Frequently asked in Amazon Directi Flipkart SAP Labs Zoho
Array Sliding Window StackViews 2419

Given an array a[ ] of size n. For every window size that varies from 1 to n in array print or find maximum of minimum for every window size in a given array.

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

Example

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

Output : 70 30 20 10 10 10 10

Input : a[ ] = {10, 20, 30}

Output : 30 20 10

Naive Method for Find Maximum of Minimum for Every Window Size

Algorithm

  1. Initialize an array a[ ] of size n.
  2. Traverse through the array a[ ]. Initialize an integer variable to store a maximum of minimum’s and set its value as INT_MIN.
  3. After that, Iterate through all the windows of the array of sizes equal to the current index of the outer loop. Initialize a variable to store the minimum of the current window and store the value at the current index in array a[ ] in it.
  4. Similarly, Traverse to find the minimum element of the array’s current window and store the minimum value in the variable to store the minimum of the current window.
  5. Check if the variable of the minimum of the current window is greater than the variable of a maximum of minimum’s, update the variable of the maximum of minimum’s as variable of the minimum of the current window.
  6. Print the variable of the maximum of the minimum.

C++ Program

#include <bits/stdc++.h> 
using namespace std; 
  
void printMaxOfMin(int a[], int n){ 
    
    for(int k=1; k<=n; k++){ 
        int maxOfMin = INT_MIN; 
  
        for(int i = 0; i <= n-k; i++){ 
            int min = a[i]; 
            for(int j = 1; j < k; j++){ 
                if(a[i+j] < min){ 
                    min = a[i+j]; 
                }
            } 
  
            if(min > maxOfMin){ 
              maxOfMin = min; 
            }
        } 
  
        cout << maxOfMin << " "; 
    } 
} 
  
int main(){ 
    int a[] = {10, 20, 30, 50, 10, 70, 30}; 
    int n = sizeof(a)/sizeof(a[0]); 
    
    printMaxOfMin(a, n); 
    
    return 0; 
}
70 30 20 10 10 10 10

Java Program

class MaxOfMin{
    
    static int a[] = {10, 20, 30, 50, 10, 70, 30}; 
      
    static void printMaxOfMin(int n){ 
        
        for(int k=1; k<=n; k++){ 
            int maxOfMin = Integer.MIN_VALUE; 
       
            for(int i = 0; i <= n-k; i++){ 
                int min = a[i]; 
                
                for(int j = 1; j < k; j++){ 
                    if(a[i+j] < min){ 
                        min = a[i+j];
                    }
                } 
       
                if(min > maxOfMin){ 
                    maxOfMin = min; 
                }
            } 
       
            System.out.print(maxOfMin + " "); 
        } 
    } 
      
    public static void main(String[] args){ 
        printMaxOfMin(a.length); 
    } 
}
70 30 20 10 10 10 10

Complexity Analysis for Find Maximum of Minimum for Every Window Size

Time Complexity: O(n3) where n is the number of elements in the given array a[ ].

Auxiliary Space: O(1) because we used constant extra space.

Efficient Method for Find Maximum of Minimum for Every Window Size

Algorithm

  1. Initialize an array a[ ] of size n.
  2. Create a stack data structure and 2 arrays left and right of length n+1. Traverse and set all the values of array left as -1 and array right as n.
  3. Traverse from 0 to n-1 and while the stack is not empty and the value in array a[ ] at index equals to the top of the stack is greater than or equal to the value in array a[ ] at current index, pop the element at the top of the stack.
  4. If the stack is not empty, update the value at the current index in an array left as the top of the stack. Push the current index in the stack.
  5. While the stack is not empty, pop the element at the top of the stack.
  6. Similarly, traverse from n-1 to 0 and while the stack is not empty and the value in array a[ ] at index equals to the top of the stack is greater than or equal to the value in array a[ ] at current index, pop the element at the top of the stack.
  7. If the stack is not empty, update the value at the current index in array right as the top of the stack. Push the current index in the stack.
  8. Create another array of size n+1 to store answers and set all of its values as 0.
  9. Traverse from 0 to n-1 and find the length of the window between values at the current index of right and left array and update the array of answers as a maximum of values at the current index of array a[ ] and at the index equal to the calculated interval of an array of answers.
  10. Print the array of answers.

C++ Program

#include <bits/stdc++.h> 
using namespace std; 
  
void printMaxOfMin(int a[], int n){ 
    
    stack<int> s;  
  
    int left[n+1];   
    int right[n+1];  
  
    for(int i=0; i<n; i++){ 
        left[i] = -1; 
        right[i] = n; 
    } 
  
    for(int i=0; i<n; i++){ 
        while(!s.empty() && a[s.top()] >= a[i]){ 
            s.pop(); 
        }
  
        if(!s.empty()){ 
            left[i] = s.top();
        }
  
        s.push(i); 
    } 
  
    while(!s.empty()){ 
        s.pop(); 
    }
  
    for(int i = n-1 ; i>=0 ; i--){ 
        while(!s.empty() && a[s.top()] >= a[i]){ 
            s.pop(); 
        }
  
        if(!s.empty()){ 
            right[i] = s.top(); 
        }
  
        s.push(i); 
    } 
  
    int ans[n+1]; 
    for(int i=0; i<=n; i++){ 
        ans[i] = 0; 
    }
  
    for(int i=0; i<n; i++){ 
        int len = right[i] - left[i] - 1; 
  
        ans[len] = max(ans[len], a[i]); 
    } 
  
    for(int i=n-1; i>=1; i--){ 
        ans[i] = max(ans[i], ans[i+1]);
    }
  
    for(int i=1; i<=n; i++){ 
        cout << ans[i] << " ";
    }
} 
  
int main(){ 
    int a[] = {10, 20, 30, 50, 10, 70, 30}; 
    int n = sizeof(a)/sizeof(a[0]); 
    
    printMaxOfMin(a, n); 
    
    return 0; 
}
70 30 20 10 10 10 10

Java Program

import java.util.Stack;

class MaxOfMin{
    
    static int a[] = {10, 20, 30, 50, 10, 70, 30}; 
      
    static void printMaxOfMin(int n){ 
        
        Stack<Integer> s = new Stack<>(); 
       
        int left[] = new int[n+1];   
        int right[]  = new int[n+1];  
       
        for(int i=0; i<n; i++){ 
            left[i] = -1; 
            right[i] = n; 
        } 
       
        for(int i=0; i<n; i++){ 
            while(!s.empty() && a[s.peek()] >= a[i]){ 
                s.pop(); 
            }
       
            if(!s.empty()){ 
                left[i] = s.peek();
            }
       
            s.push(i); 
        } 
       
        while(!s.empty()){ 
            s.pop(); 
        }
       
        for(int i = n-1 ; i>=0 ; i--){ 
            while(!s.empty() && a[s.peek()] >= a[i]){ 
                s.pop(); 
            }
       
            if(!s.empty()){ 
                right[i] = s.peek(); 
            }
       
            s.push(i); 
        } 
       
        int ans[] = new int[n+1]; 
        for(int i=0; i<=n; i++){ 
            ans[i] = 0; 
        }
       
        for(int i=0; i<n; i++){ 
            int len = right[i] - left[i] - 1; 
            ans[len] = Math.max(ans[len], a[i]); 
        } 
       
        for(int i=n-1; i>=1; i--){ 
            ans[i] = Math.max(ans[i], ans[i+1]);
        }
       
        for(int i=1; i<=n; i++){ 
            System.out.print(ans[i] + " "); 
        }
    } 
      
    public static void main(String[] args){ 
        printMaxOfMin(a.length); 
    } 
}
70 30 20 10 10 10 10

Complexity Analysis for Find Maximum of Minimum for Every Window Size

Time Complexity: O(n) where n is the number of elements in the given array a[ ].

Auxiliary Space: O(n) because we used stack space for n elements.

References

Translate »