Maximum of Minimum for Every Window Size — Solution
Maximum of Minimum for Every Window Size solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum of Minimum for Every Window Size is a hard coding problem on arrays, stack and sliding window, asked in Amazon, Microsoft and Flipkart interviews.
- Difficulty: Hard
- Topics: Arrays, Stack, Sliding Window, Monotonic Stack
- Asked at: Amazon, Microsoft, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
For every window size k from 1 to n, look at all n - k + 1 contiguous windows of arr of that size, take the minimum of each window, and then the maximum of those minimums.
Return an array res of length n where res[k - 1] is that value for window size k.
Example 1
Input: arr = [3,8,5,1,6]
Output: [8,5,3,1,1]
Explanation: Size 2: the windows' minimums are 3, 5, 1, 1 — the largest is 5. Size 3: 3, 1, 1 — the largest is 3.
Example 2
Input: arr = [4,4,4]
Output: [4,4,4]
Example 3
Input: arr = [2,9,9,2,7]
Output: [9,9,2,2,2]
Constraints
1 <= arr.length <= 10^51 <= arr[i] <= 10^6
Hints for Maximum of Minimum for Every Window Size
Hint 1
Turn it around: for each element, what is the largest window in which it is the minimum?
Hint 2
That window stretches from just after the previous smaller element to just before the next smaller element — a monotonic stack gives both in O(n).
Hint 3
If
arr[i]is the minimum of a window of lengthL, it is a candidate for sizeLand also for every smaller size (shrink the window around it). Record the best per exact length, then sweep from long to short taking running maximums.
How to solve Maximum of Minimum for Every Window Size
Each element is the minimum of exactly one maximal window. Recording its value at that window's length, then propagating maximums from longer to shorter lengths, answers every size at once.
Approach
- With a monotonic stack compute
left[i](previous index with a smaller value, or -1) andright[i](next index with a smaller-or-equal value, orn). - The length
L = right[i] - left[i] - 1window hasarr[i]as its minimum; setbest[L] = max(best[L], arr[i]). - For
Lfromn - 1down to1, setbest[L] = max(best[L], best[L + 1]). - Return
best[1..n].
Why it works
The answer for size k is some window minimum arr[i]. That element's maximal window has length >= k, and any length-k sub-window containing i still has minimum arr[i], so the value is achievable for size k — which is what the backward sweep propagates. Conversely every recorded value is a real window minimum. With equal values, stopping at a smaller-or-equal element on the right only shortens the windows of earlier copies; the last copy still gets the full length.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The answers are non-increasing in
k; forgetting the backward sweep leaves sizes that no element 'owns' at their initial value. - Window length is
right - left - 1, with the sentinels -1 andn. - The brute-force O(n²) double loop is fine for small inputs but not for 10^5.
Reference solution
Python
from typing import List
def maxOfMins(arr: List[int]) -> List[int]:
n = len(arr)
left = [-1] * n
right = [n] * n
st = []
for i in range(n):
while st and arr[st[-1]] >= arr[i]:
right[st.pop()] = i
left[i] = st[-1] if st else -1
st.append(i)
best = [0] * (n + 2)
for i in range(n):
length = right[i] - left[i] - 1
best[length] = max(best[length], arr[i])
for length in range(n - 1, 0, -1):
best[length] = max(best[length], best[length + 1])
return best[1:n + 1]Java
public static int[] maxOfMins(int[] arr) {
int n = arr.length;
int[] left = new int[n], right = new int[n], st = new int[n];
int top = 0;
for (int i = 0; i < n; i++) {
right[i] = n;
while (top > 0 && arr[st[top - 1]] >= arr[i]) right[st[--top]] = i;
left[i] = top > 0 ? st[top - 1] : -1;
st[top++] = i;
}
int[] best = new int[n + 2];
for (int i = 0; i < n; i++) {
int len = right[i] - left[i] - 1;
best[len] = Math.max(best[len], arr[i]);
}
for (int k = n - 1; k >= 1; k--) best[k] = Math.max(best[k], best[k + 1]);
return Arrays.copyOfRange(best, 1, n + 1);
}C++
vector<int> maxOfMins(vector<int>& arr) {
int n = arr.size();
vector<int> left(n, -1), right(n, n), st;
for (int i = 0; i < n; i++) {
while (!st.empty() && arr[st.back()] >= arr[i]) {
right[st.back()] = i;
st.pop_back();
}
left[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
vector<int> best(n + 2, 0);
for (int i = 0; i < n; i++) {
int len = right[i] - left[i] - 1;
best[len] = max(best[len], arr[i]);
}
for (int k = n - 1; k >= 1; k--) best[k] = max(best[k], best[k + 1]);
return vector<int>(best.begin() + 1, best.begin() + n + 1);
}JavaScript
var maxOfMins = function(arr) {
var n = arr.length;
var left = new Array(n).fill(-1), right = new Array(n).fill(n), st = [];
for (var i = 0; i < n; i++) {
while (st.length > 0 && arr[st[st.length - 1]] >= arr[i]) right[st.pop()] = i;
left[i] = st.length > 0 ? st[st.length - 1] : -1;
st.push(i);
}
var best = new Array(n + 2).fill(0);
for (var j = 0; j < n; j++) {
var len = right[j] - left[j] - 1;
if (arr[j] > best[len]) best[len] = arr[j];
}
for (var k = n - 1; k >= 1; k--) if (best[k + 1] > best[k]) best[k] = best[k + 1];
return best.slice(1, n + 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure