Max of min for every window size

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

For each window size k (1..n), find the maximum of the minimum values in all windows of size k.

Algorithm

1For each element: find the nearest smaller to left (L[i]) and right (R[i]) using monotonic stack.
2Element arr[i] is min for windows of size 1..R[i]-L[i]-1. Use this to fill answer array, then propagate max backwards.

Common Pitfalls

•Same as "Maximum of minimums of every window size". O(n) with two monotonic stack passes + backward propagation.

Max of min for every window size.java

Java

// Approach: For each element, find previous and next smaller element (monotonic stack) to determine its window range.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public ArrayList<Integer> maxOfMins(int[] arr) {
        int n = arr.length;
        int[] res = new int[n];
        int[] lenArr = new int[n];
        Stack<Integer> s = new Stack<>();

        for (int i = 0; i < n; i++) {
            while (!s.isEmpty() && arr[s.peek()] >= arr[i]) {
                int top = s.pop();
                int windowSize = s.isEmpty() ? i : i - s.peek() - 1;
                lenArr[top] = windowSize;
            }
            s.push(i);
        }

        while (!s.isEmpty()) {
            int top = s.pop();
            int windowSize = s.isEmpty() ? n : n - s.peek() - 1;
            lenArr[top] = windowSize;
        }

        for (int i = 0; i < n; i++) {
            int windowSize = lenArr[i];
            if (windowSize > 0)
                res[windowSize - 1] = Math.max(res[windowSize - 1], arr[i]);
        }

        for (int i = n - 2; i >= 0; i--)
            res[i] = Math.max(res[i], res[i + 1]);

        ArrayList<Integer> ans = new ArrayList<>();
        for (int val : res)
            ans.add(val);

        return ans;
    }
}

Was this solution helpful?