Loading…

hardStack QueueSometimes asked

Min Max Riddle

Q: How do you solve Min Max Riddle using the Brute Force — Every Window of Every Size approach?

When to use it: State it to anchor the problem, then immediately note it's O(n²) (or O(n³) naively) and will TLE for n = 10⁵. The literal reading: for each window size `w` from 1 to n, examine every length-`w` window, compute its minimum, and keep the maximum of those minimums. **Why it's the natural first attempt.** It mirrors the problem statement one-to-one — two nested loops over (size, start position) plus a min. There's no insight required, just enumeration. **Making the inner min cheap.** For a fixed size, sliding the window one step changes only the entering and leaving elements. A monotonic deque tracks the window minimum in amortised O(1), so each size is O(n) and the whole thing is O(n²). Without that, recomputing the min from scratch makes it O(n³). **Why we don't ship it.** At n = 10⁵, O(n²) is ~10¹⁰ operations — a guaranteed timeout. It's useful only as a correctness oracle to test the optimal solution against on small inputs. Time complexity: O(n²). Space complexity: O(n).

Stack & Queue · 13 of 17 · 11 min

You are given an array arr of n integers. For a window (contiguous subarray) you take its minimum. For every window size from 1 to n, consider all windows of that size and take the maximum of their minimums.

Return an array of n values where the value at index w − 1 is the maximum-of-minimums over all windows of size w.

In plain English

For each window length we want the best (largest) achievable minimum. A large element can only be a window's minimum inside the stretch where no smaller element intrudes — that stretch is its 'span'. The longest window in which arr[i] is the minimum has length equal to the distance between the nearest strictly-smaller elements on each side. That length is the largest window size for which arr[i] is a candidate answer; it also qualifies for all shorter sizes.

Examples

Example 1

Input: arr = [6, 3, 5, 1, 12]
Output: [12, 3, 3, 1, 1]
Note: Size 1: max element 12. Size 2: best window-min is 3 (from [6,3] or [3,5]). Size 3: 3 (from [6,3,5]). Size 4: 1. Size 5: 1 (whole array min).

Example 2

Input: arr = [2, 6, 1, 12]
Output: [12, 2, 1, 1]
Note: Size 1: 12. Size 2: windows mins 2,1,1 → max 2. Size 3: mins 1,1 → 1. Size 4: 1.

Example 3

Input: arr = [3, 5, 4, 7, 6, 2]
Output: [7, 6, 4, 4, 3, 2]
Note: Size 1: 7. Size 2: best min 6 (from [7,6]). Size 3: 4 (from [5,4,7] or [4,7,6]). Size 4: 4. Size 5: 3. Size 6: 2.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ arr[i] ≤ 10⁹
Output has exactly n values (one per window size 1..n)
An O(n²) solution times out — O(n) or O(n log n) is required

Clarifying questions4First question: Output one value per window size, 1 through n?Explore questions

Q1.Output one value per window size, 1 through n?
Yes — n values total. Index 0 is window size 1 (the global max element), index n−1 is window size n (the global min).
Q2.Can values repeat?
Yes. Handle ties consistently in the stack (pop on ≥) so a run of equal values isn't double-counted in spans.
Q3.Is the largest window size's answer just the global minimum?
Yes. The only window of size n is the whole array, whose minimum is the array's minimum.
Q4.Why does a length-L answer also count for smaller lengths?
If arr[i] is the minimum of some length-L window, it's also the minimum of sub-windows of that window of every smaller size, so it remains a candidate for those sizes.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

For each window size w from 1..n, output the maximum over all length-w windows of that window's minimum. Don't enumerate windows. Instead, for each element find the largest window in which it is the minimum (its span between the previous-smaller and next-smaller elements) using a monotonic stack; that element is a candidate answer for that span length. Take the max per length, then sweep from large lengths down to small so every size inherits the best of any larger feasible span. O(n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can flip an O(n²)-over-windows problem into an O(n) per-element span computation with a monotonic stack, and reason about the 'a length-L answer also serves all smaller lengths' sweep.

Where candidates slip

Brute-forcing all windows (TLE for n up to 10⁵), getting the span boundaries wrong, or forgetting the descending sweep so smaller window sizes are left too small.

How to stand out

Name the previous-smaller / next-smaller monotonic-stack technique, explain why the largest span an element wins as min answers that length, and justify the descending max-propagation in one sentence.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Every Window of Every Size	`O(n²)`	`O(n)`	State it to anchor the problem, then immediately note it's O(n²) (or O(n³) naively) and will TLE for n = 10⁵.	Read
2	Monotonic Stack — Span of Dominance (Optimal)Optimal	`O(n)`	`O(n)`	The intended solution. Explain previous-smaller / next-smaller spans and the descending max-sweep.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Span-of-dominance pipeline

How to read it:Monotonic stacks give each element's span; map span→max element; sweep down so smaller sizes inherit.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Every Window of Every Size

TimeO(n²)SpaceO(n)

State it to anchor the problem, then immediately note it's O(n²) (or O(n³) naively) and will TLE for n = 10⁵.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Directly translate the definition: for each window size w, slide a window across and track its minimum.

2Hint 2Explore hint

Maintaining the running minimum as the window slides keeps each size at O(n), giving O(n²) overall.

3Hint 3Explore hint

n up to 10⁵ means n² ≈ 10¹⁰ operations — far too slow. This frames why we need the stack approach.

A · Core idea

The literal reading: for each window size w from 1 to n, examine every length-w window, compute its minimum, and keep the maximum of those minimums.

Why it's the natural first attempt. It mirrors the problem statement one-to-one — two nested loops over (size, start position) plus a min. There's no insight required, just enumeration.

Making the inner min cheap. For a fixed size, sliding the window one step changes only the entering and leaving elements. A monotonic deque tracks the window minimum in amortised O(1), so each size is O(n) and the whole thing is O(n²). Without that, recomputing the min from scratch makes it O(n³).

Why we don't ship it. At n = 10⁵, O(n²) is ~10¹⁰ operations — a guaranteed timeout. It's useful only as a correctness oracle to test the optimal solution against on small inputs.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [2, 6, 1, 12]

Array state

size 2 win 0

[2,6] min = 2

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result[12, 2, 1, 1]

C · Code with teaching comments

Reference implementation previewpublic long[] riddleBrute(long[] arr) { int n = arr.length; long[] ans = new long[n]; for (int w = 1; w <= n; w++) { long best = Long.MIN_VALUE;Explore the full code

solution.javaJava

Brute Force — Every Window of Every Size — reference

4 teaching notes

1
public long[] riddleBrute(long[] arr) {
2
    int n = arr.length;
3
    long[] ans = new long[n];
4
    // Outer loop over every window size 1..n.
5
    for (int w = 1; w <= n; w++) {
6
        long best = Long.MIN_VALUE;
7
        // Every start position for a window of this size.
8
        for (int s = 0; s + w <= n; s++) {
9
            long mn = Long.MAX_VALUE;
10
            for (int k = s; k < s + w; k++) {
11
                // Compute the window's minimum (the inner loop is what makes it O(n³)
12
                // here).
13
                mn = Math.min(mn, arr[k]);
14
            }
15
            best = Math.max(best, mn);
16
        }
17
        // Store the max-of-mins for this size (1-indexed size → 0-indexed array).
18
        ans[w - 1] = best;
19
    }
20
    return ans;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

Brute force re-derives each window's minimum independently and so repeats enormous work. The optimal flips the question: rather than 'what is each window's min?', ask 'for each element, which windows is it the min of?' — answered once per element with a stack.

ComplexityO(n²) time, O(n) space — n window sizes × O(n) work to scan windows of that size = O(n²). With a naive inner min recomputation it degrades to O(n³).

E · Edge cases and pitfalls5arr = [5] — Only size 1; ans = [5].Explore edge cases

Edge cases handled

arr = [5]Only size 1; ans = [5].
arr = [4, 4]size 1 → 4, size 2 → min(4,4)=4 → [4, 4].

Pitfalls

Recomputing the min from scratch for every window — O(n³), worse than necessary.
Off-by-one in the start bound: use s + w <= n.
Believing it will pass — n = 10⁵ guarantees a timeout.

03.2

Approach 2 of 2 · Optimal

Monotonic Stack — Span of Dominance (Optimal)

TimeO(n)SpaceO(n)

The intended solution. Explain previous-smaller / next-smaller spans and the descending max-sweep.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of asking each window for its minimum, ask each element: what is the longest window in which I am the minimum?

2Hint 2Explore hint

An element stays the minimum until a strictly smaller element appears on its left or right. Find the nearest smaller element on each side with a monotonic stack.

3Hint 3Explore hint

If arr[i]'s span (between nearest smaller neighbours) has length L, then arr[i] is a candidate answer for window size L — and for every size below L. Take per-size maxima, then propagate from large sizes down to small.

A · Core idea

Turn the problem inside out. Rather than computing each window's minimum, determine for each element the largest window in which it is the minimum.

The span of an element. arr[i] is the minimum of a window exactly while no smaller value is inside that window. So extend left until you hit the nearest element strictly smaller than arr[i] (call its index prevSmaller[i]), and right until the nearest strictly smaller element (nextSmaller[i]). The widest window where arr[i] reigns as minimum has length len = nextSmaller[i] − prevSmaller[i] − 1.

Computing prev/next smaller in O(n). A monotonic increasing stack does both. Scanning left to right, before pushing i we pop every index whose value is ≥ arr[i]; whatever remains on top is the previous strictly-smaller element (or −1 if the stack empties). A symmetric right-to-left scan gives nextSmaller (boundary n). Each index is pushed and popped once, so it's linear.

Mapping spans to answers. For each i, arr[i] is a valid candidate for window size len. Record ans[len] = max(ans[len], arr[i]). Multiple elements can share a length; we keep the largest.

The descending sweep — the subtle finish. An element that is the minimum of a length-L window is also the minimum of sub-windows of every smaller size within it, so it is a candidate for all sizes ≤ L. After filling ans[len] directly, sweep from w = n−1 down to 1 doing ans[w] = max(ans[w], ans[w+1]). This lets a strong answer found at a large length flow down to fill any smaller size that didn't get a bigger candidate of its own.

Handling ties. Popping on ≥ (not >) in both passes assigns each window of equal-valued runs to a single representative, preventing a value from being counted as the minimum of an overlapping span twice. The per-size max is unaffected because the true best still wins, but it keeps spans clean.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [6, 3, 5, 1, 12]

Array state

element 3 @ i=1

prevSmaller=-1, nextSmaller=3 → span length 3

[0]

i ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result[12, 3, 3, 1, 1]

C · Code with teaching comments

solution.javaJava

Monotonic Stack — Span of Dominance (Optimal) — optimal

6 teaching notes

1
import java.util.*;
2
 
3
public long[] riddle(long[] arr) {
4
    int n = arr.length;
5
    int[] prevSmaller = new int[n];
6
    int[] nextSmaller = new int[n];
7
    Deque<Integer> stack = new ArrayDeque<>();
8
 
9
    for (int i = 0; i < n; i++) {
10
        // Pop indices whose value is >= current — leaves the previous strictly-smaller
11
        // on top.
12
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
13
            stack.pop();
14
        }
15
        // Nearest smaller index on the left, or -1 boundary if none.
16
        prevSmaller[i] = stack.isEmpty() ? -1 : stack.peek();
17
        stack.push(i);
18
    }
19
 
20
    stack.clear();
21
    for (int i = n - 1; i >= 0; i--) {
22
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
23
            stack.pop();
24
        }
25
        // Symmetric right-to-left scan; boundary n when no smaller element to the
26
        // right.
27
        nextSmaller[i] = stack.isEmpty() ? n : stack.peek();
28
        stack.push(i);
29
    }
30
 
31
    long[] ans = new long[n + 2];
32
    for (int i = 0; i < n; i++) {
33
        // Largest window length in which arr[i] is the minimum.
34
        int len = nextSmaller[i] - prevSmaller[i] - 1;
35
        // arr[i] is a candidate answer for window size len.
36
        ans[len] = Math.max(ans[len], arr[i]);
37
    }
38
    for (int w = n - 1; w >= 1; w--) {
39
        // Descending sweep: a length-(w+1) answer also serves size w.
40
        ans[w] = Math.max(ans[w], ans[w + 1]);
41
    }
42
 
43
    long[] result = new long[n];
44
    for (int w = 1; w <= n; w++) {
45
        result[w - 1] = ans[w];
46
    }
47
    return result;
48
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.48 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

The pivot from 'minimum of each window' to 'span where each element is the minimum' is the entire trick — and it's the same monotonic-stack span idea behind Largest Rectangle in Histogram and Sum of Subarray Minimums. Once you see 'nearest smaller on both sides', a whole family of O(n²)-looking problems collapse to O(n).

ComplexityO(n) time, O(n) space — Each element is pushed and popped from the stack at most once across both passes → O(n). The final descending sweep is O(n). Arrays of size n → O(n) space.

E · Edge cases and pitfalls8arr = [5] — prevSmaller=-1, nextSmaller=1 → span 1 → ans[1]=5 → [5].Explore edge cases

Edge cases handled

arr = [5]prevSmaller=-1, nextSmaller=1 → span 1 → ans[1]=5 → [5].
arr = [4, 4]With ≥-pops, spans give ans[1]=4 and the whole-array min sweep yields [4, 4].
arr = [1, 2, 3, 4, 5]Increasing: element 5 has span 1, element 1 span 5 → [5, 4, 3, 2, 1].

Pitfalls

Mixing up the span formula — it's nextSmaller − prevSmaller − 1, not nextSmaller − prevSmaller.
Skipping the descending sweep — smaller window sizes are left at 0 or too small.
Using > instead of ≥ inconsistently across the two passes, double-counting equal runs.
Sweeping in ascending order — answers must flow from large sizes DOWN to small ones.
Using int sums for values up to 10⁹ where products overflow (here we only compare, so long is safe; still prefer long).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; public long[] riddle(long[] arr) { int n = arr.length; int[] prevSmaller = new int[n];Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

public long[] riddle(long[] arr) {
    int n = arr.length;
    int[] prevSmaller = new int[n];
    int[] nextSmaller = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();

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

stack.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
            stack.pop();
        }
        nextSmaller[i] = stack.isEmpty() ? n : stack.peek();
        stack.push(i);
    }

long[] ans = new long[n + 2];
    for (int i = 0; i < n; i++) {
        int len = nextSmaller[i] - prevSmaller[i] - 1;
        ans[len] = Math.max(ans[len], arr[i]);
    }
    for (int w = n - 1; w >= 1; w--) {
        ans[w] = Math.max(ans[w], ans[w + 1]);
    }

long[] result = new long[n];
    for (int w = 1; w <= n; w++) {
        result[w - 1] = ans[w];
    }
    return result;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping the descending sweep

Directly assigning ans[span] only fills the exact largest length each element wins. Smaller sizes that lack their own large candidate stay zero. A length-L answer is valid for all sizes ≤ L, so you must propagate downward.

Explore the code comparison

Don't write this

for i in range(n):
    length = next_smaller[i] - prev_smaller[i] - 1
    ans[length] = max(ans[length], arr[i])
return ans[1:n + 1]   # smaller sizes may still be 0

Write this instead

for i in range(n):
    length = next_smaller[i] - prev_smaller[i] - 1
    ans[length] = max(ans[length], arr[i])
for w in range(n - 1, 0, -1):
    ans[w] = max(ans[w], ans[w + 1])
return ans[1:n + 1]

Wrong span boundary formula

The span counts elements strictly between the two smaller neighbours. Using nextSmaller − prevSmaller overcounts by one and misassigns elements to a window size one too large.

Explore the code comparison

Don't write this

int len = nextSmaller[i] - prevSmaller[i];      // off by one
ans[len] = Math.max(ans[len], arr[i]);

Write this instead

int len = nextSmaller[i] - prevSmaller[i] - 1;
ans[len] = Math.max(ans[len], arr[i]);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Monotonic stack → span where each element is the minimum

Code pattern to memorize

For each i: span = nextSmaller[i] - prevSmaller[i] - 1
ans[span] = max(ans[span], arr[i])
for w from n-1 down to 1: ans[w] = max(ans[w], ans[w+1])

Rules to remember

1Each element arr[i] is the minimum of every window contained in its span (prevSmaller, nextSmaller); the largest such window has length nextSmaller − prevSmaller − 1.
2An element that is the answer for window length L is also a valid candidate for every length smaller than L — hence the final descending sweep.
3Compute previous-smaller and next-smaller indices with a monotonic increasing stack, popping while the stacked value is ≥ the current value.
4Use a boundary of -1 on the left and n on the right for elements with no smaller neighbour.
5Answer array is 1-indexed by window size; ans[w] is the result for windows of size w.

Use this pattern when

'For every window size, the max/min of window mins/maxes' style aggregate queries
You need the span in which each element dominates as the min (or max)
Histogram / largest-rectangle relatives where each bar's reach matters
Any time brute force is O(n²) over windows and you want O(n) via spans

Choose another pattern when

A single fixed window size → sliding-window deque (Sliding Window Maximum), not per-size spans
You need the actual windows, not just the aggregate → spans don't reconstruct them directly
Values can repeat heavily and you need exact counts → be careful with ≥ vs > to avoid double-count

Interview takeaway

Replace 'iterate every window' with 'for each element, what is the largest window where it's the minimum?'. A monotonic stack gives every element's span in O(n); a descending max-sweep then fills all smaller sizes. This span-of-dominance idea powers Largest Rectangle and Sum of Subarray Minimums too.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternMonotonic-stack span-of-dominance: for each element find the nearest strictly-smaller neighbours, derive the largest window it's the min of, then propagate answers from large window sizes down to small. Same machinery as Largest Rectangle and Sum of Subarray Minimums.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Largest Rectangle in Histogram
Coming soon
Same nearest-smaller spans: each bar's width × height; take the max area.
Sum of Subarray Minimums
Coming soon
Count subarrays where each element is the minimum via prev/next smaller spans, weighted sum.
Sliding Window Maximum
Coming soon
Fixed window size instead of all sizes — monotonic deque, not per-size spans.

Same pattern

←

Maximum Element

Continue · Next problem

Simple Text Editor

hardStack QueueSometimes asked

Min Max Riddle

Stack & Queue · 13 of 17 · 11 min

Return an array of n values where the value at index w − 1 is the maximum-of-minimums over all windows of size w.

In plain English

Examples

Example 1

Input: arr = [6, 3, 5, 1, 12]
Output: [12, 3, 3, 1, 1]
Note: Size 1: max element 12. Size 2: best window-min is 3 (from [6,3] or [3,5]). Size 3: 3 (from [6,3,5]). Size 4: 1. Size 5: 1 (whole array min).

Example 2

Input: arr = [2, 6, 1, 12]
Output: [12, 2, 1, 1]
Note: Size 1: 12. Size 2: windows mins 2,1,1 → max 2. Size 3: mins 1,1 → 1. Size 4: 1.

Example 3

Input: arr = [3, 5, 4, 7, 6, 2]
Output: [7, 6, 4, 4, 3, 2]
Note: Size 1: 7. Size 2: best min 6 (from [7,6]). Size 3: 4 (from [5,4,7] or [4,7,6]). Size 4: 4. Size 5: 3. Size 6: 2.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ arr[i] ≤ 10⁹
Output has exactly n values (one per window size 1..n)
An O(n²) solution times out — O(n) or O(n log n) is required

Clarifying questions4First question: Output one value per window size, 1 through n?Explore questions

Q1.Output one value per window size, 1 through n?
Yes — n values total. Index 0 is window size 1 (the global max element), index n−1 is window size n (the global min).
Q2.Can values repeat?
Yes. Handle ties consistently in the stack (pop on ≥) so a run of equal values isn't double-counted in spans.
Q3.Is the largest window size's answer just the global minimum?
Yes. The only window of size n is the whole array, whose minimum is the array's minimum.
Q4.Why does a length-L answer also count for smaller lengths?
If arr[i] is the minimum of some length-L window, it's also the minimum of sub-windows of that window of every smaller size, so it remains a candidate for those sizes.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can flip an O(n²)-over-windows problem into an O(n) per-element span computation with a monotonic stack, and reason about the 'a length-L answer also serves all smaller lengths' sweep.

Where candidates slip

Brute-forcing all windows (TLE for n up to 10⁵), getting the span boundaries wrong, or forgetting the descending sweep so smaller window sizes are left too small.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Every Window of Every Size	`O(n²)`	`O(n)`	State it to anchor the problem, then immediately note it's O(n²) (or O(n³) naively) and will TLE for n = 10⁵.	Read
2	Monotonic Stack — Span of Dominance (Optimal)Optimal	`O(n)`	`O(n)`	The intended solution. Explain previous-smaller / next-smaller spans and the descending max-sweep.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Span-of-dominance pipeline

How to read it:Monotonic stacks give each element's span; map span→max element; sweep down so smaller sizes inherit.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Every Window of Every Size

TimeO(n²)SpaceO(n)

State it to anchor the problem, then immediately note it's O(n²) (or O(n³) naively) and will TLE for n = 10⁵.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Directly translate the definition: for each window size w, slide a window across and track its minimum.

2Hint 2Explore hint

Maintaining the running minimum as the window slides keeps each size at O(n), giving O(n²) overall.

3Hint 3Explore hint

n up to 10⁵ means n² ≈ 10¹⁰ operations — far too slow. This frames why we need the stack approach.

A · Core idea

The literal reading: for each window size w from 1 to n, examine every length-w window, compute its minimum, and keep the maximum of those minimums.

Why it's the natural first attempt. It mirrors the problem statement one-to-one — two nested loops over (size, start position) plus a min. There's no insight required, just enumeration.

Why we don't ship it. At n = 10⁵, O(n²) is ~10¹⁰ operations — a guaranteed timeout. It's useful only as a correctness oracle to test the optimal solution against on small inputs.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [2, 6, 1, 12]

Array state

size 2 win 0

[2,6] min = 2

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result[12, 2, 1, 1]

C · Code with teaching comments

Reference implementation previewpublic long[] riddleBrute(long[] arr) { int n = arr.length; long[] ans = new long[n]; for (int w = 1; w <= n; w++) { long best = Long.MIN_VALUE;Explore the full code

solution.javaJava

Brute Force — Every Window of Every Size — reference

4 teaching notes

1
public long[] riddleBrute(long[] arr) {
2
    int n = arr.length;
3
    long[] ans = new long[n];
4
    // Outer loop over every window size 1..n.
5
    for (int w = 1; w <= n; w++) {
6
        long best = Long.MIN_VALUE;
7
        // Every start position for a window of this size.
8
        for (int s = 0; s + w <= n; s++) {
9
            long mn = Long.MAX_VALUE;
10
            for (int k = s; k < s + w; k++) {
11
                // Compute the window's minimum (the inner loop is what makes it O(n³)
12
                // here).
13
                mn = Math.min(mn, arr[k]);
14
            }
15
            best = Math.max(best, mn);
16
        }
17
        // Store the max-of-mins for this size (1-indexed size → 0-indexed array).
18
        ans[w - 1] = best;
19
    }
20
    return ans;
21
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.21 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(n) space — n window sizes × O(n) work to scan windows of that size = O(n²). With a naive inner min recomputation it degrades to O(n³).

E · Edge cases and pitfalls5arr = [5] — Only size 1; ans = [5].Explore edge cases

Edge cases handled

arr = [5]Only size 1; ans = [5].
arr = [4, 4]size 1 → 4, size 2 → min(4,4)=4 → [4, 4].

Pitfalls

Recomputing the min from scratch for every window — O(n³), worse than necessary.
Off-by-one in the start bound: use s + w <= n.
Believing it will pass — n = 10⁵ guarantees a timeout.

03.2

Approach 2 of 2 · Optimal

Monotonic Stack — Span of Dominance (Optimal)

TimeO(n)SpaceO(n)

The intended solution. Explain previous-smaller / next-smaller spans and the descending max-sweep.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Instead of asking each window for its minimum, ask each element: what is the longest window in which I am the minimum?

2Hint 2Explore hint

An element stays the minimum until a strictly smaller element appears on its left or right. Find the nearest smaller element on each side with a monotonic stack.

3Hint 3Explore hint

A · Core idea

Turn the problem inside out. Rather than computing each window's minimum, determine for each element the largest window in which it is the minimum.

Mapping spans to answers. For each i, arr[i] is a valid candidate for window size len. Record ans[len] = max(ans[len], arr[i]). Multiple elements can share a length; we keep the largest.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

arr = [6, 3, 5, 1, 12]

Array state

element 3 @ i=1

prevSmaller=-1, nextSmaller=3 → span length 3

[0]

i ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result[12, 3, 3, 1, 1]

C · Code with teaching comments

solution.javaJava

Monotonic Stack — Span of Dominance (Optimal) — optimal

6 teaching notes

1
import java.util.*;
2
 
3
public long[] riddle(long[] arr) {
4
    int n = arr.length;
5
    int[] prevSmaller = new int[n];
6
    int[] nextSmaller = new int[n];
7
    Deque<Integer> stack = new ArrayDeque<>();
8
 
9
    for (int i = 0; i < n; i++) {
10
        // Pop indices whose value is >= current — leaves the previous strictly-smaller
11
        // on top.
12
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
13
            stack.pop();
14
        }
15
        // Nearest smaller index on the left, or -1 boundary if none.
16
        prevSmaller[i] = stack.isEmpty() ? -1 : stack.peek();
17
        stack.push(i);
18
    }
19
 
20
    stack.clear();
21
    for (int i = n - 1; i >= 0; i--) {
22
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
23
            stack.pop();
24
        }
25
        // Symmetric right-to-left scan; boundary n when no smaller element to the
26
        // right.
27
        nextSmaller[i] = stack.isEmpty() ? n : stack.peek();
28
        stack.push(i);
29
    }
30
 
31
    long[] ans = new long[n + 2];
32
    for (int i = 0; i < n; i++) {
33
        // Largest window length in which arr[i] is the minimum.
34
        int len = nextSmaller[i] - prevSmaller[i] - 1;
35
        // arr[i] is a candidate answer for window size len.
36
        ans[len] = Math.max(ans[len], arr[i]);
37
    }
38
    for (int w = n - 1; w >= 1; w--) {
39
        // Descending sweep: a length-(w+1) answer also serves size w.
40
        ans[w] = Math.max(ans[w], ans[w + 1]);
41
    }
42
 
43
    long[] result = new long[n];
44
    for (int w = 1; w <= n; w++) {
45
        result[w - 1] = ans[w];
46
    }
47
    return result;
48
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.48 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — Each element is pushed and popped from the stack at most once across both passes → O(n). The final descending sweep is O(n). Arrays of size n → O(n) space.

E · Edge cases and pitfalls8arr = [5] — prevSmaller=-1, nextSmaller=1 → span 1 → ans[1]=5 → [5].Explore edge cases

Edge cases handled

arr = [5]prevSmaller=-1, nextSmaller=1 → span 1 → ans[1]=5 → [5].
arr = [4, 4]With ≥-pops, spans give ans[1]=4 and the whole-array min sweep yields [4, 4].
arr = [1, 2, 3, 4, 5]Increasing: element 5 has span 1, element 1 span 5 → [5, 4, 3, 2, 1].

Pitfalls

Mixing up the span formula — it's nextSmaller − prevSmaller − 1, not nextSmaller − prevSmaller.
Skipping the descending sweep — smaller window sizes are left at 0 or too small.
Using > instead of ≥ inconsistently across the two passes, double-counting equal runs.
Sweeping in ascending order — answers must flow from large sizes DOWN to small ones.
Using int sums for values up to 10⁹ where products overflow (here we only compare, so long is safe; still prefer long).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; public long[] riddle(long[] arr) { int n = arr.length; int[] prevSmaller = new int[n];Explore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

public long[] riddle(long[] arr) {
    int n = arr.length;
    int[] prevSmaller = new int[n];
    int[] nextSmaller = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();

long[] result = new long[n];
    for (int w = 1; w <= n; w++) {
        result[w - 1] = ans[w];
    }
    return result;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Skipping the descending sweep

Explore the code comparison

Don't write this

for i in range(n):
    length = next_smaller[i] - prev_smaller[i] - 1
    ans[length] = max(ans[length], arr[i])
return ans[1:n + 1]   # smaller sizes may still be 0

Write this instead

for i in range(n):
    length = next_smaller[i] - prev_smaller[i] - 1
    ans[length] = max(ans[length], arr[i])
for w in range(n - 1, 0, -1):
    ans[w] = max(ans[w], ans[w + 1])
return ans[1:n + 1]

Wrong span boundary formula

The span counts elements strictly between the two smaller neighbours. Using nextSmaller − prevSmaller overcounts by one and misassigns elements to a window size one too large.

Explore the code comparison

Don't write this

int len = nextSmaller[i] - prevSmaller[i];      // off by one
ans[len] = Math.max(ans[len], arr[i]);

Write this instead

int len = nextSmaller[i] - prevSmaller[i] - 1;
ans[len] = Math.max(ans[len], arr[i]);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Monotonic stack → span where each element is the minimum

Code pattern to memorize

For each i: span = nextSmaller[i] - prevSmaller[i] - 1
ans[span] = max(ans[span], arr[i])
for w from n-1 down to 1: ans[w] = max(ans[w], ans[w+1])

Rules to remember

1Each element arr[i] is the minimum of every window contained in its span (prevSmaller, nextSmaller); the largest such window has length nextSmaller − prevSmaller − 1.
2An element that is the answer for window length L is also a valid candidate for every length smaller than L — hence the final descending sweep.
3Compute previous-smaller and next-smaller indices with a monotonic increasing stack, popping while the stacked value is ≥ the current value.
4Use a boundary of -1 on the left and n on the right for elements with no smaller neighbour.
5Answer array is 1-indexed by window size; ans[w] is the result for windows of size w.

Use this pattern when

'For every window size, the max/min of window mins/maxes' style aggregate queries
You need the span in which each element dominates as the min (or max)
Histogram / largest-rectangle relatives where each bar's reach matters
Any time brute force is O(n²) over windows and you want O(n) via spans

Choose another pattern when

A single fixed window size → sliding-window deque (Sliding Window Maximum), not per-size spans
You need the actual windows, not just the aggregate → spans don't reconstruct them directly
Values can repeat heavily and you need exact counts → be careful with ≥ vs > to avoid double-count

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Largest Rectangle in Histogram
Coming soon
Same nearest-smaller spans: each bar's width × height; take the max area.
Sum of Subarray Minimums
Coming soon
Count subarrays where each element is the minimum via prev/next smaller spans, weighted sum.
Sliding Window Maximum
Coming soon
Fixed window size instead of all sizes — monotonic deque, not per-size spans.

Same pattern

←

Maximum Element

Continue · Next problem

Simple Text Editor