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.
Table of Contents
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
- Initialize an array a[ ] of size n.
- Traverse through the array a[ ]. Initialize an integer variable to store a maximum of minimum’s and set its value as INT_MIN.
- 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.
- 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.
- 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.
- 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
- Initialize an array a[ ] of size n.
- 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.
- 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.
- 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.
- While the stack is not empty, pop the element at the top of the stack.
- 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.
- 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.
- Create another array of size n+1 to store answers and set all of its values as 0.
- 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.
- 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.