GeeksforGeeks Medium

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.

stackmonotonic-stacksliding-window

02

Intuition

💡

Flip the question per element: for how large a window is a[i] the minimum? Exactly the stretch between its previous-smaller and next-smaller neighbours. Each element then bids for that window size; propagate bids down to smaller sizes.

03

Approach

1

Previous & next smaller via stacks

Two monotonic-stack passes give, for each i, the nearest smaller element on each side — the window where a[i] rules as minimum has length len = next[i] − prev[i] − 1.

2

Bid on the answer array

ans[len] = max(ans[len], a[i]): the best minimum achievable for that exact window length.

3

Fill gaps right-to-left

A great minimum for length L also works for any shorter window inside it, so ans[k] = max(ans[k], ans[k+1]) sweeping down.

04

Solution & live demo

python

▶1def max_of_mins(a):
▶2    n = len(a)
▶3    prev, nxt = [-1] * n, [n] * n
▶4    stack = []
▶5    for i in range(n):                      # previous smaller
▶6        while stack and a[stack[-1]] >= a[i]: stack.pop()
▶7        prev[i] = stack[-1] if stack else -1
▶8        stack.append(i)
▶9    stack = []
▶10    for i in range(n - 1, -1, -1):          # next smaller
▶11        while stack and a[stack[-1]] > a[i]: stack.pop()
▶12        nxt[i] = stack[-1] if stack else n
▶13        stack.append(i)
▶14    ans = [0] * (n + 1)
▶15    for i in range(n):
▶16        length = nxt[i] - prev[i] - 1
▶17        ans[length] = max(ans[length], a[i])
▶18    for k in range(n - 1, 0, -1):
▶19        ans[k] = max(ans[k], ans[k + 1])
▶20    return ans[1:]

05

Edge cases

Strictly increasing array

Each element's window runs to the right edge; the sweep fills every size correctly.

Duplicates

Use strict inequality on one side only to avoid double-counting equal spans.

06

Complexity

Time

O(n)

Space

O(n)

Three linear passes, two monotonic stacks.