Maximum of Minimums for Every Window Size
For every window size 1..n, find the maximum over all windows of that size of the window's minimum.
- 1 <= n <= 10⁵
- 1 <= nums[i] <= 10⁹
- Answer has exactly n entries, one per window size
Intuition
The maximum of minimums for every window size problem asks, for each window length from 1 to n, for the largest minimum any window of that length achieves. Computing it directly means examining every window of every size — O(n²) windows, and worse if each minimum is scanned.
The way in is to turn the question around. Instead of asking "for this window size, which element is the minimum?", ask of each element:
- What is the largest window in which a[i] is the minimum?
That has a precise answer. Element a[i] stays the minimum as long as the window contains no smaller value, so it extends from just after the previous smaller element to just before the next smaller element. If those sit at indices prev[i] and next[i], the window length is next[i] − prev[i] − 1.
Both boundaries come from monotonic stacks in two linear passes — the same technique as Next Greater Element with the comparison flipped.
Each element then bids: for its window length L, the answer is at least a[i]. Take the maximum bid per length.
One final step is easy to miss. If a value is achievable as the minimum for length L, it is also achievable for any shorter window, since a shorter window fits inside the longer one and its minimum can only be larger or equal. So sweep the answer array from the largest length down, propagating each value leftward.
Invert the question. Instead of asking each window for its minimum, ask each element for the largest window in which it is the minimum — that span runs between its previous-smaller and next-smaller elements, both from monotonic stacks. A final suffix-max pass fills sizes no element claimed directly.
Approach
Before reading on: price up what the direct approach costs here, then ask what ordering you can maintain so the answer is always at one end. Aim for O(n) time and O(n) space.
Invert the question per element
Rather than scanning each window, ask how large a window each element can dominate. This converts an O(n²) search over windows into an O(n) computation over elements, which is the whole idea.
Find previous and next smaller with stacks
Two monotonic-stack passes give, for each index, the nearest strictly smaller element to its left and right. Out of bounds counts as −1 and n respectively, so an element with nothing smaller beside it spans the whole array.
Compute each element's dominion
The window where a[i] is the minimum has length next[i] - prev[i] - 1. Within that span no value is smaller, and extending one step further would include one — so this is exactly the largest window a[i] rules.
Record the best bid per length
Set ans[len] = max(ans[len], a[i]). Several elements may bid for the same length and only the largest matters, since the problem asks for the maximum minimum.
Propagate answers to shorter windows
Sweep from n down to 1 with ans[k] = max(ans[k], ans[k+1]). A minimum achievable at length L is achievable at any shorter length, because the shorter window sits inside the longer one — without this pass, lengths that no element bid for are left empty.
Cost of the three passes
Two stack passes and two linear sweeps give O(n) time, with each index pushed and popped at most once. Space is O(n) for the boundary arrays and the answer array.
Solution & live demo
Common pitfalls
Computing every window explicitly
for k in range(1, n + 1):
ans[k] = max(min(a[i:i+k]) for i in range(n - k + 1))length = nxt[i] - prev[i] - 1 ans[length] = max(ans[length], a[i])
That's O(n³). Each element is the minimum of exactly one maximal span, so computing that span with two stack passes answers every window size in O(n).
Skipping the suffix-maximum pass
return ans[1:]
for k in range(n - 1, 0, -1):
ans[k] = max(ans[k], ans[k + 1])
return ans[1:]Some window sizes are never any element's maximal span and are left at 0. But an element that is the minimum of a length-5 window is also the minimum of some length-4 window inside it, so answers propagate downward from larger sizes.
Using the same strictness in both stack passes
while stack and a[stack[-1]] >= a[i]: pop # in both loops
# previous smaller: >= # next smaller: >
With equal values, using the same comparison on both sides makes two identical elements claim overlapping spans and one of them is measured too short. Making one side strict and the other non-strict assigns each span to exactly one representative.
Edge cases
Each element's window runs to the right edge; the sweep fills every size correctly.
Use strict inequality on one side only to avoid double-counting equal spans.