Given an integer array arr[], find the maximum of minimums for every window size from 1 to n. For each window size k, consider all contiguous subarrays of length k and determine the minimum element in each subarray. Among these minimum values, take the maximum one.
Example:
Input: arr[] = [10, 20, 30]
Output: [30, 20, 10]
Explanation: The max of min for every possible window size.
Size 1: min of [10], [20], [30], max of min is 30.
Size 2: min of [10, 20],[20,30] max of min is 20.
Size 3: min of [10,20,30], max of min is 10.Input: arr[] = [10, 20, 30, 50, 10, 70, 30]
Output: [70, 30, 20, 10, 10, 10, 10]
Explanation:
Size 1: min are [10, 20, 30, 50, 10, 70, 30], max of min is 70.
Size 2: min are [10, 20, 30, 10, 10, 30], max of min is 30.
Size 3: min are [10, 20, 10, 10, 10], max of min is 20.
Size 4–7: min are [10, 10, 10, 10], max of min is 10.
Try it on GfG Practice
Table of Content
[Naive Approach] By Checking All Subarrays O(n^3) Time and O(1) Space
Compute the minimum of every possible window, For each window size from 1 to n and find the maximum of those minimums.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
vector<int> maxOfMin(vector<int>& arr) {
int n = arr.size();
vector<int> res(n);
// for each window size k
for (int k = 1; k <= n; k++) {
int maxMin = INT_MIN;
// slide window of size k
for (int i = 0; i <= n - k; i++) {
int minval = INT_MAX;
// find minimum in current window
for (int j = i; j < i + k; j++) {
minval = min(minval, arr[j]);
}
maxMin = max(maxMin, minval);
}
res[k - 1] = maxMin;
}
return res;
}
int main() {
vector<int> arr = {10, 20, 30, 50, 10, 70, 30};
vector<int> res = maxOfMin(arr);
for (int val : res) cout << val << " ";
cout << endl;
return 0;
}
import java.util.ArrayList;
public class GfG {
public static ArrayList<Integer> maxOfMin(int[] arr) {
int n = arr.length;
ArrayList<Integer> res = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
res.add(0);
}
// For each window size k
for (int k = 1; k <= n; k++) {
int maxMin = Integer.MIN_VALUE;
// Slide window of size k
for (int i = 0; i <= n - k; i++) {
int minVal = Integer.MAX_VALUE;
// Find minimum in current window
for (int j = i; j < i + k; j++) {
minVal = Math.min(minVal, arr[j]);
}
maxMin = Math.max(maxMin, minVal);
}
res.set(k - 1, maxMin);
}
return res;
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 50, 10, 70, 30};
int n = arr.length;
ArrayList<Integer> res = maxOfMin(arr);
for (int val : res) {
System.out.print(val + " ");
}
System.out.println();
}
}
def maxOfMin(arr):
n = len(arr)
res = [0] * n
# For each window size k
for k in range(1, n + 1):
maxMin = float('-inf')
# Slide window of size k
for i in range(n - k + 1):
minval = float('inf')
# Find minimum in current window
for j in range(i, i + k):
minval = min(minval, arr[j])
maxMin = max(maxMin, minval)
# Store result for window size k
res[k - 1] = maxMin
return res
if __name__ == "__main__":
arr = [10, 20, 30, 50, 10, 70, 30]
n = len(arr)
res = maxOfMin(arr)
print(" ".join(map(str, res)))
using System;
using System.Collections.Generic;
class GfG {
public static List<int> maxOfMin(int[] arr) {
int n = arr.Length;
List<int> res = new List<int>(new int[n]);
// for each window size k
for (int k = 1; k <= n; k++) {
int maxMin = int.MinValue;
// slide window of size k
for (int i = 0; i <= n - k; i++) {
int minVal = int.MaxValue;
// find minimum in current window
for (int j = i; j < i + k; j++) {
minVal = Math.Min(minVal, arr[j]);
}
maxMin = Math.Max(maxMin, minVal);
}
res[k - 1] = maxMin;
}
return res;
}
public static void Main(string[] args) {
int[] arr = { 10, 20, 30, 50, 10, 70, 30 };
int n = arr.Length;
List<int> res = maxOfMin(arr);
Console.Write(string.Join(" ", res));
Console.WriteLine();
}
}
function maxOfMin(arr) {
const n = arr.length;
const res = new Array(n).fill(0);
// Consider all windows of different sizes
// starting from size 1
for (let k = 1; k <= n; k++) {
let maxOfMin = -Infinity;
// Traverse through all windows of current size k
for (let i = 0; i <= n - k; i++) {
// Find minimum of current window
let minVal = arr[i];
for (let j = 1; j < k; j++) {
minVal = Math.min(minVal, arr[i + j]);
}
// Update maxOfMin if required
maxOfMin = Math.max(maxOfMin, minVal);
}
// Store max of min for current window size
res[k - 1] = maxOfMin;
}
return res;
}
// Driver program
const arr = [10, 20, 30, 50, 10, 70, 30];
const res = maxOfMin(arr);
console.log(res.join(" "));
Output
70 30 20 10 10 10 10
[Better Approach] Sliding Window Minimum using Deque - O(n^2) Time and O(n) Space
Use a deque with the sliding window technique to find the minimum element of every subarray of size k efficiently. Repeat this for k = 1 to n, and for each k, take the maximum among these minimum values.
#include <iostream>
#include <vector>
#include <deque>
#include <climits>
using namespace std;
vector<int> maxOfMin(vector<int>& arr) {
int n = arr.size();
vector<int> res(n);
// iterate over all window sizes
for (int k = 1; k <= n; k++) {
deque<int> dq;
int maxMin = INT_MIN;
// process first k elements
for (int i = 0; i < k; i++) {
while (!dq.empty() && arr[i] <= arr[dq.back()])
dq.pop_back();
dq.push_back(i);
}
// slide the window
for (int i = k; i < n; i++) {
maxMin = max(maxMin, arr[dq.front()]);
while (!dq.empty() && dq.front() <= i - k)
dq.pop_front();
while (!dq.empty() && arr[i] <= arr[dq.back()])
dq.pop_back();
dq.push_back(i);
}
maxMin = max(maxMin, arr[dq.front()]);
res[k - 1] = maxMin;
}
return res;
}
int main() {
vector<int> arr = {10, 20, 30, 50, 10, 70, 30};
vector<int> res = maxOfMin(arr);
for (int val : res) cout << val << " ";
cout << endl;
return 0;
}
import java.util.Deque;
import java.util.ArrayList;
import java.util.ArrayDeque;
class GfG {
static ArrayList<Integer> maxOfMin(int arr[]) {
int n = arr.length;
ArrayList<Integer> res = new ArrayList<>();
// iterate over all window sizes
for (int k = 1; k <= n; k++) {
Deque<Integer> dq = new ArrayDeque<>();
int maxMin = Integer.MIN_VALUE;
// process first k elements
for (int i = 0; i < k; i++) {
while (!dq.isEmpty() && arr[i] <= arr[dq.peekLast()])
dq.pollLast();
dq.offerLast(i);
}
// slide the window
for (int i = k; i < n; i++) {
maxMin = Math.max(maxMin, arr[dq.peekFirst()]);
while (!dq.isEmpty() && dq.peekFirst() <= i - k)
dq.pollFirst();
while (!dq.isEmpty() && arr[i] <= arr[dq.peekLast()])
dq.pollLast();
dq.offerLast(i);
}
maxMin = Math.max(maxMin, arr[dq.peekFirst()]);
res.add(maxMin);
}
return res;
}
public static void main(String[] args) {
int arr[] = {10, 20, 30, 50, 10, 70, 30};
ArrayList<Integer> res = maxOfMin(arr);
for (int val : res) System.out.print(val + " ");
System.out.println();
}
}
from collections import deque
import sys
def maxOfMin(arr):
n = len(arr);
res = []
# iterate over all window sizes
for k in range(1, n + 1):
dq = deque()
maxMin = -sys.maxsize
# process first k elements
for i in range(k):
while dq and arr[i] <= arr[dq[-1]]:
dq.pop()
dq.append(i)
# slide the window
for i in range(k, n):
maxMin = max(maxMin, arr[dq[0]])
while dq and dq[0] <= i - k:
dq.popleft()
while dq and arr[i] <= arr[dq[-1]]:
dq.pop()
dq.append(i)
maxMin = max(maxMin, arr[dq[0]])
res.append(maxMin)
return res
if __name__ == "__main__":
arr = [10, 20, 30, 50, 10, 70, 30]
res = maxOfMin(arr)
for val in res:
print(val, end=" ")
print()
using System;
using System.Collections.Generic;
class GfG {
static List<int> maxOfMin(int[] arr) {
int n = arr.Length;
List<int> res = new List<int>();
// iterate over all window sizes
for (int k = 1; k <= n; k++) {
LinkedList<int> dq = new LinkedList<int>();
int maxMin = int.MinValue;
// process first k elements
for (int i = 0; i < k; i++) {
while (dq.Count > 0 && arr[i] <= arr[dq.Last.Value])
dq.RemoveLast();
dq.AddLast(i);
}
// slide the window
for (int i = k; i < n; i++) {
maxMin = Math.Max(maxMin, arr[dq.First.Value]);
while (dq.Count > 0 && dq.First.Value <= i - k)
dq.RemoveFirst();
while (dq.Count > 0 && arr[i] <= arr[dq.Last.Value])
dq.RemoveLast();
dq.AddLast(i);
}
maxMin = Math.Max(maxMin, arr[dq.First.Value]);
res.Add(maxMin);
}
return res;
}
public static void Main() {
int[] arr = {10, 20, 30, 50, 10, 70, 30};
List<int> res = maxOfMin(arr);
foreach (int val in res) Console.Write(val + " ");
Console.WriteLine();
}
}
function maxOfMin(arr) {
let n = arr.length;
let res = [];
// iterate over all window sizes
for (let k = 1; k <= n; k++) {
let dq = [];
let maxMin = Number.MIN_SAFE_INTEGER;
// process first k elements
for (let i = 0; i < k; i++) {
while (dq.length > 0 && arr[i] <= arr[dq[dq.length - 1]])
dq.pop();
dq.push(i);
}
// slide the window
for (let i = k; i < n; i++) {
maxMin = Math.max(maxMin, arr[dq[0]]);
while (dq.length > 0 && dq[0] <= i - k)
dq.shift();
while (dq.length > 0 && arr[i] <= arr[dq[dq.length - 1]])
dq.pop();
dq.push(i);
}
maxMin = Math.max(maxMin, arr[dq[0]]);
res.push(maxMin);
}
return res;
}
// Driver Code
let arr = [10, 20, 30, 50, 10, 70, 30];
let res = maxOfMin(arr);
console.log(res.join(" "));
Output
70 30 20 10 10 10 10
[Expected Approach] Using Stack - O(n) Time and O(n) Space
- For each element, find the previous smaller and next smaller using a stack.
- These boundaries give the largest window size where the current element is the minimum.
- Update the answer for that window size with the maximum value of such minimums.
- Finally, propagate results backward so smaller windows have at least as large values as larger windows.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> maxOfMin(vector<int>& arr) {
int n = arr.size();
vector<int> res(n), len(n + 1, 0);
stack<int> st;
// find window sizes for each element
for (int i = 0; i < n; i++) {
while (!st.empty() && arr[st.top()] >= arr[i]) {
int top = st.top();
st.pop();
int left = st.empty() ? -1 : st.top();
int right = i;
int windowSize = right - left - 1;
len[windowSize] = max(len[windowSize], arr[top]);
}
st.push(i);
}
// process remaining elements in stack
while (!st.empty()) {
int top = st.top();
st.pop();
int left = st.empty() ? -1 : st.top();
int right = n;
int windowSize = right - left - 1;
len[windowSize] = max(len[windowSize], arr[top]);
}
for (int i = 1; i <= n; i++) {
res[i - 1] = len[i];
}
for (int i = n - 2; i >= 0; i--) {
res[i] = max(res[i], res[i + 1]);
}
return res;
}
int main() {
vector<int> arr = {10, 20, 30, 50, 10, 70, 30};
vector<int> res = maxOfMin(arr);
for (int val : res) cout << val << " ";
cout << endl;
return 0;
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Arrays;
class GfG {
static ArrayList<Integer> maxOfMin(int[] arr) {
int n = arr.length;
ArrayList<Integer> res =
new ArrayList<>(Collections.nCopies(n, 0));
ArrayList<Integer> len =
new ArrayList<>(Collections.nCopies(n + 1, 0));
Deque<Integer> stack = new ArrayDeque<>();
// Compute previous and next smaller elements using monotonic stack
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
int top = stack.pop();
int left = stack.isEmpty() ? -1 : stack.peek();
int right = i;
int windowSize = right - left - 1;
len.set(windowSize,
Math.max(len.get(windowSize), arr[top]));
}
stack.push(i);
}
// Process remaining elements
while (!stack.isEmpty()) {
int top = stack.pop();
int left = stack.isEmpty() ? -1 : stack.peek();
int right = n;
int windowSize = right - left - 1;
len.set(windowSize,
Math.max(len.get(windowSize), arr[top]));
}
// Fill result using len[]
for (int i = 1; i <= n; i++) {
res.set(i - 1, len.get(i));
}
// Ensure result is non-increasing
for (int i = n - 2; i >= 0; i--) {
res.set(i, Math.max(res.get(i), res.get(i + 1)));
}
return res;
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 50, 10, 70, 30};
ArrayList<Integer> res = maxOfMin(arr);
for (int val : res) {
System.out.print(val + " ");
}
System.out.println();
}
}
def maxOfMin(arr):
n = len(arr)
res = [0] * n
windowMax = [0] * (n + 1)
st = []
# Find previous and next smaller elements
for i in range(n):
while st and arr[st[-1]] >= arr[i]:
top = st.pop()
left = st[-1] if st else -1
right = i
wsize = right - left - 1
windowMax[wsize] = max(windowMax[wsize], arr[top])
st.append(i)
# Process remaining elements in the stack
while st:
top = st.pop()
left = st[-1] if st else -1
right = n
wsize = right - left - 1
windowMax[wsize] = max(windowMax[wsize], arr[top])
# Fill the result list
for i in range(n):
res[i] = windowMax[i + 1]
# Ensure results are non-increasing
for i in range(n - 2, -1, -1):
res[i] = max(res[i], res[i + 1])
return res
if __name__ == "__main__":
arr = [10, 20, 30, 50, 10, 70, 30]
result = maxOfMin(arr)
print(" ".join(map(str, result)))
using System;
using System.Collections.Generic;
class GfG {
static List<int> maxOfMin(int[] arr) {
int n = arr.Length;
List<int> res = new List<int>(new int[n]);
int[] windowMax = new int[n + 1];
Stack<int> st = new Stack<int>();
// find window sizes for each element
for (int i = 0; i < n; i++) {
while (st.Count > 0 && arr[st.Peek()] >= arr[i]) {
int top = st.Pop();
int left = st.Count == 0 ? -1 : st.Peek();
int right = i;
int windowSize = right - left - 1;
windowMax[windowSize] = Math.Max(windowMax[windowSize], arr[top]);
}
st.Push(i);
}
// process remaining elements in stack
while (st.Count > 0) {
int top = st.Pop();
int left = st.Count == 0 ? -1 : st.Peek();
int right = n;
int windowSize = right - left - 1;
windowMax[windowSize] = Math.Max(windowMax[windowSize], arr[top]);
}
for (int i = 0; i < n; i++) {
res[i] = windowMax[i + 1];
}
for (int i = n - 2; i >= 0; i--) {
res[i] = Math.Max(res[i], res[i + 1]);
}
return res;
}
static void Main() {
int[] arr = { 10, 20, 30, 50, 10, 70, 30 };
List<int> res = maxOfMin(arr);
foreach (int val in res)
Console.Write(val + " ");
Console.WriteLine();
}
}
function maxOfMin(arr) {
const n = arr.length;
const res = new Array(n).fill(0);
const windowMax = new Array(n + 1).fill(0);
const st = [];
// find window sizes for each element
for (let i = 0; i < n; i++) {
while (st.length && arr[st[st.length - 1]] >= arr[i]) {
const top = st.pop();
const left = st.length ? st[st.length - 1] : -1;
const right = i;
const windowSize = right - left - 1;
windowMax[windowSize] = Math.max(windowMax[windowSize], arr[top]);
}
st.push(i);
}
// process remaining elements in stack
while (st.length) {
const top = st.pop();
const left = st.length ? st[st.length - 1] : -1;
const right = n;
const windowSize = right - left - 1;
windowMax[windowSize] = Math.max(windowMax[windowSize], arr[top]);
}
// build result array
for (let i = 0; i < n; i++) {
res[i] = windowMax[i + 1];
}
// ensure non-increasing order
for (let i = n - 2; i >= 0; i--) {
res[i] = Math.max(res[i], res[i + 1]);
}
return res;
}
// Driver Code
const arr = [10, 20, 30, 50, 10, 70, 30];
const res = maxOfMin(arr);
console.log(res.join(' '));
Output
70 30 20 10 10 10 10