☕ DSA Java Articles

Topics › Stacks and Queues › Monotonic Stack/Queue Problems [VVV. Imp]

Maximum of Minimums for Every Window Size

Medium TUF ID 687 SDE

Java source ↗ Edit this article ↗

Problem

You are given an array arr of n integers. For every window size k from 1 to n, look at all contiguous windows (subarrays) of length k, take the minimum of each window, and report the maximum of those minimums. Return the n answers as an array where position k - 1 holds the answer for size k.

Constraints: 1 ≤ n ≤ 10^5, values fit in an int and may repeat.

Example 1

arr = [10, 20, 30, 50, 10, 70, 30]
answer = [70, 30, 20, 10, 10, 10, 10]
// size 1: the windows are single elements, best is 70
// size 2: minimums 10, 20, 30, 10, 10, 30, best is 30
// size 3: minimums 10, 20, 10, 10, 10, best is 20
// sizes 4 to 7: every window contains a 10, best is 10

Example 2

arr = [10, 20, 30]
answer = [30, 20, 10]

Approach 1: Brute force, every window from scratch

Intuition. Follow the definition literally: for each size, for each starting position, compute the window’s minimum with a loop, and keep the best. It is easy to trust, which makes it the reference the tests compare against, but it repeats a lot of work.

Algorithm.

  1. For k = 1..n: set best = -∞.
  2. For each start with start + k ≤ n: compute the minimum of arr[start..start+k-1] and update best.
  3. Store best as the answer for size k.
static int[] bruteForce(int[] arr) {
    int n = arr.length;
    int[] ans = new int[n];
    for (int k = 1; k <= n; k++) {
        int best = Integer.MIN_VALUE;
        for (int start = 0; start + k <= n; start++) {
            int min = Integer.MAX_VALUE;
            for (int i = start; i < start + k; i++) min = Math.min(min, arr[i]);
            best = Math.max(best, min);
        }
        ans[k - 1] = best;
    }
    return ans;
}

Complexity. Time O(n^3): about n^2 / 2 windows, each scanned in O(n). Space O(1) besides the output.

Approach 2: Better, extend windows with a running minimum

Intuition. Windows that share a left end overlap heavily. If we know the minimum of arr[start..end], the minimum of arr[start..end+1] is just min(previous, arr[end+1]). So fix the left end and grow the window one element at a time; each step produces the minimum of a new window in O(1), and that window’s length tells us which answer slot it competes for.

Algorithm.

  1. Fill the answer array with -∞.
  2. For each start: set min = +∞; for each end ≥ start, update min with arr[end] and set ans[len - 1] = max(ans[len - 1], min) where len = end - start + 1.
static int[] better(int[] arr) {
    int n = arr.length;
    int[] ans = new int[n];
    Arrays.fill(ans, Integer.MIN_VALUE);
    for (int start = 0; start < n; start++) {
        int min = Integer.MAX_VALUE;
        for (int end = start; end < n; end++) {
            min = Math.min(min, arr[end]);             // minimum of arr[start..end]
            int len = end - start + 1;
            ans[len - 1] = Math.max(ans[len - 1], min);
        }
    }
    return ans;
}

Complexity. Time O(n^2): every window is visited once in O(1). Space O(1) besides the output. Still too slow for n = 10^5.

Approach 3: Optimal, monotonic stack

Intuition. Turn the question around. Instead of asking “for each window, what is its minimum?”, ask “for each element, which windows is it the minimum of?”.

Let left[i] be the index of the previous element strictly smaller than arr[i] (or -1), and right[i] the index of the next element strictly smaller (or n). Every element strictly between them is ≥ arr[i], so arr[i] is the minimum of every window that contains i and stays inside (left[i], right[i]). The widest such window has length len = right[i] - left[i] - 1.

Two facts finish the argument:

So the answer for size k is the largest arr[i] among the elements with len ≥ k. Compute that by recording each arr[i] at slot len, then sweeping from the largest size down to the smallest, carrying the maximum along. The sweep also reflects a simple truth: the answers can only get smaller as k grows, since any window of size k + 1 contains a window of size k whose minimum is at least as large.

Both boundary arrays come from the classic monotonic stack: scanning left to right, pop every index whose value is ≥ arr[i]; whatever remains on top is the previous strictly smaller element. Scan right to left for the next smaller element.

Algorithm.

  1. Compute left[] and right[] with a monotonic stack each.
  2. For each i, len = right[i] - left[i] - 1, and ans[len - 1] = max(ans[len - 1], arr[i]).
  3. For k from n - 2 down to 0: ans[k] = max(ans[k], ans[k + 1]).
static int[] optimal(int[] arr) {
    int n = arr.length;
    int[] left = new int[n], right = new int[n];      // index of previous / next strictly smaller element
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && arr[st.peek()] >= arr[i]) st.pop();
        left[i] = st.isEmpty() ? -1 : st.peek();
        st.push(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.isEmpty() && arr[st.peek()] >= arr[i]) st.pop();
        right[i] = st.isEmpty() ? n : st.peek();
        st.push(i);
    }
    int[] ans = new int[n];
    Arrays.fill(ans, Integer.MIN_VALUE);
    for (int i = 0; i < n; i++) {
        int len = right[i] - left[i] - 1;              // widest window in which arr[i] is the minimum
        ans[len - 1] = Math.max(ans[len - 1], arr[i]);
    }
    for (int k = n - 2; k >= 0; k--) {
        ans[k] = Math.max(ans[k], ans[k + 1]);         // a smaller window fits inside a bigger one
    }
    return ans;
}

Dry run on Example 1:

i arr[i] left right len
0 10 -1 7 7
1 20 0 4 3
2 30 1 4 2
3 50 2 4 1
4 10 -1 7 7
5 70 4 6 1
6 30 4 7 2

Recording by size gives size 1 → max(50, 70) = 70, size 2 → max(30, 30) = 30, size 3 → 20, size 7 → max(10, 10) = 10, and nothing for sizes 4 to 6. The right-to-left sweep fills sizes 4 to 6 from size 7, producing [70, 30, 20, 10, 10, 10, 10].

Complexity. Time O(n): each index is pushed and popped at most once per scan, and the final sweep is linear. Space O(n) for the two boundary arrays and the stack.

Edge cases and pitfalls