Max of min for every window size

Problem Statement

geeksforgeeks.org

Given an array of size N, for every window size from:

1 → N

find:

Maximum of all minimum elements

for that window size.

---

Brute Force Intuition

In an interview, you can explain it like this:

For every possible window size, generate all windows. Compute the minimum of each window and keep track of the maximum among those minimums.

This repeatedly computes minimums for overlapping windows.

Complexity

• Time Complexity: O(N³)
• Space Complexity: O(1)

Brute Force Code

class Solution {

    public int[] maxOfMin(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 i = 0; i <= n - k; i++) {

                int min = Integer.MAX_VALUE;

                for (int j = i; j < i + k; j++) {

                    min = Math.min(min, arr[j]);
                }

                best = Math.max(best, min);
            }

            ans[k - 1] = best;
        }

        return ans;
    }
}

---

Moving Towards the Optimal Approach

Instead of checking every window,

ask a different question.

For every element:

In how many window sizes
can this element be
the minimum?

If we know that,

we can directly update the answer.

---

Pattern Recognition

Whenever you see:

• Previous Smaller
• Next Smaller
• Range where an element dominates

Think:

Monotonic Stack

---

Key Observation

Suppose:

Array

10 20 30 50 10 70 30

Take:

30

Find:

Previous Smaller

↓

Next Smaller

These two indices tell us:

Maximum window size
where 30 remains
the minimum element.

Window Length:

length = nextSmaller
       - prevSmaller
       - 1;

Now simply update:

answer[length]
=
max(answer[length],30);

---

Optimal Approach

Step 1

Find:

Previous Smaller Index

---

Step 2

Find:

Next Smaller Index

---

Step 3

For every element:

length = right - left - 1

Update:

ans[length]

---

Step 4

Some window sizes may remain empty.

Fill them from right to left:

ans[i] = Math.max(ans[i],
                  ans[i+1]);

---

Optimal Java Solution

class Solution {

    public int[] maxOfMin(int[] arr) {

        int n = arr.length;

        int[] left = new int[n];
        int[] right = new int[n];

        Stack<Integer> st = new Stack<>();

        // Previous Smaller
        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();

        // Next Smaller
        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 + 1];

        Arrays.fill(ans, Integer.MIN_VALUE);

        for (int i = 0; i < n; i++) {

            int len =
                right[i] - left[i] - 1;

            ans[len] =
                Math.max(ans[len], arr[i]);
        }

        for (int i = n - 1; i >= 1; i--) {

            ans[i] =
                Math.max(ans[i], ans[i + 1]);
        }

        return Arrays.copyOfRange(ans, 1, n + 1);
    }
}

---

Dry Run

Input

arr = [10,20,30,50,10,70,30]

---

Previous Smaller

-1

0

1

2

-1

4

4

---

Next Smaller

7

4

4

4

7

6

7

---

Window Lengths

For:

50

Window:

4 - 2 - 1

= 1

Update:

ans[1] = 50

For:

30

Window:

4 - 1 - 1

= 2

Update:

ans[2] = 30

Continue similarly.

---

Final Answer

70 30 20 10 10 10 10

---

Why Monotonic Stack Works?

Every element is:

Pushed Once

Popped Once

The stack efficiently finds the previous and next smaller elements.

From these boundaries, we know exactly the largest window where an element is the minimum.

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(N)

---

Interview One-Liner

Compute the previous and next smaller indices for every element to determine the largest window where it is the minimum, then update the answer for that window size.

---

Pattern Learned

Previous Smaller

+

Next Smaller

↓

Window Length

↓

Monotonic Stack

Similar Problems

• Maximum of Minimum for Every Window Size
• Largest Rectangle in Histogram
• Sum of Subarray Minimums
• Next Smaller Element
• Previous Smaller Element

---

Memory Trick

Think:

Current Element

↓

Previous Smaller

↓

Next Smaller

↓

Largest Window

↓

Update Answer

Mental Model

Element

↓

Acts as Minimum

↓

For One Window Length

↓

Store Best Value

Whenever you hear:

"Maximum of minimums" or "Range where an element is minimum"

your brain should immediately think:

Previous Smaller + Next Smaller + Monotonic Stack