How do you solve Maximum Element using the Auxiliary Max Stack (Optimal) approach?

When to use it: The answer they want. Describe the parallel stack invariant: its top is always the current maximum. Maintain two stacks of equal height: the main stack of values, and a `maxStack` whose top is always the maximum of everything currently in the main stack. **The invariant.** After every operation, `maxStack.peek()` equals the maximum of the main stack. We preserve it on each operation: - **Push x:** push `x` onto the main stack and push `max(x, maxStack.peek())` onto `maxStack`. The new running max is either the old max or `x`, whichever is larger. When the stack was empty, the previous max is `−∞`, so we just push `x`. - **Pop:** pop both stacks. Removing the top value also removes the max-so-far that it introduced, restoring `maxStack`'s top to the maximum of the remaining elements — which is exactly the value that was there before this element was pushed. - **Max query:** return `maxStack.peek()`. **Why store `max(x, prevMax)` and not just `x`.** The max stack at depth `d` must answer 'what is the largest value among the bottom `d` elements?'. Storing the running max at each depth makes that a single read. Storing raw values would force a scan, defeating the purpose. **Why popping both keeps it correct.** The two stacks always have the same height and were filled in lockstep, so the element at depth `d` in `maxStack` corresponds to the prefix of depth `d` in the main stack. Popping both unwinds exactly one push, and the new top of `maxStack` is the max of the new (shorter) prefix. **Why it's O(1).** Push, pop, and peek on a stack are all constant time, and we do a fixed number of them per query. No scanning, ever. Time complexity: O(1) per query. Space complexity: O(n).

Loading…

easyStack QueueFrequently asked

Maximum Element

Q: How do you solve Maximum Element using the Brute Force — Scan the Stack on Every Max Query approach?

When to use it: Mention to motivate the optimal, then note the O(n) per query cost violates the O(1) requirement. Keep a single stack. Push and pop normally. For a max query, walk every element and return the largest. **Why it's the obvious first cut.** Push and pop are the native stack operations and need nothing extra. The maximum *is* derivable from the contents, so scanning answers it correctly. **Why it fails the bar.** The problem explicitly wants O(1) max queries. A scan is O(n) per query; with q and n both up to 10⁵ that's up to 10¹⁰ operations and a timeout. It's correct but unacceptably slow — useful only to frame why we precompute the running max. Time complexity: O(q·n). Space complexity: O(n).

Stack & Queue · 12 of 17 · 8 min

You have an empty stack. Process q queries, each of one of three types:

1 x — push the integer x onto the stack.
2 — pop the element on top of the stack.
3 — print the maximum element currently in the stack.

All type-3 queries must run in O(1). Print the answer to each type-3 query on its own line.

In plain English

Support push, pop, and 'current maximum' on a stack, all in O(1). The maximum can only be affected at the top: pushing may raise it, popping may lower it back to what it was before that element. That history of 'max so far at each depth' is exactly what a parallel stack records.

Examples

Example 1

Input: queries = ["1 97", "2", "1 20", "2", "1 26", "1 20", "2", "3", "1 91", "3"]
Output: 26 91
Note: After the pops, the stack holds [26]; max = 26. Then push 91 → stack [26, 91]; max = 91.

Example 2

Input: queries = ["1 4", "1 7", "3", "2", "3"]
Output: 7 4
Note: Push 4, push 7 → max 7. Pop 7 → stack [4] → max 4.

Example 3

Input: queries = ["1 5", "1 5", "3", "2", "3"]
Output: 5 5
Note: Duplicates: max stays 5 after pushing two 5s and after popping one.

Constraints

1 ≤ q ≤ 10⁵
1 ≤ x ≤ 10⁹
Type 2 (pop) is only issued when the stack is non-empty
Type 3 (max) is only issued when the stack is non-empty
Each operation must be O(1)

Clarifying questions4First question: Can the max query happen on an empty stack?Explore questions

Q1.Can the max query happen on an empty stack?
No — the constraints guarantee type-3 (and type-2) queries only occur when the stack is non-empty, so we don't special-case emptiness for them.
Q2.Must each query be O(1), or is O(n) per query acceptable?
O(1) is required. With q up to 10⁵, an O(n) scan per max query risks O(n²) and a timeout.
Q3.Can values repeat?
Yes. The max stack handles duplicates naturally because it stores the running max, which simply stays the same across equal values.
Q4.Could I store the max only when it changes, to save space?
You could (an index/count-based variant), but the full parallel stack is simpler and still O(n) space — fine for these limits.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Back a normal stack with a second 'max stack' that mirrors the running maximum. On push, also push max(newValue, currentMax) onto the max stack. On pop, pop both. The current maximum is always the top of the max stack — O(1) per push, pop, and max query.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can achieve O(1) max queries by maintaining an auxiliary stack of running maxima, instead of scanning the stack on every query.

Where candidates slip

Recomputing the max by scanning the whole stack on each query (O(n) per query → O(nq) total), or pushing the raw value onto the max stack instead of max(value, previousMax).

How to stand out

State the auxiliary-max-stack invariant (its top equals the current maximum), show push/pop keep both stacks the same height, and note this is the same idea as Min Stack.

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 — Scan the Stack on Every Max Query	`O(q·n)`	`O(n)`	Mention to motivate the optimal, then note the O(n) per query cost violates the O(1) requirement.	Read
2	Auxiliary Max Stack (Optimal)Optimal	`O(1) per query`	`O(n)`	The answer they want. Describe the parallel stack invariant: its top is always the current maximum.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewquerytype?1 x (push)2 (pop)Explore the full tree

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 — Scan the Stack on Every Max Query

TimeO(q·n)SpaceO(n)

Mention to motivate the optimal, then note the O(n) per query cost violates the O(1) requirement.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Push and pop are trivially O(1) on a stack. The only hard part is the max query.

2Hint 2Explore hint

The simplest max query iterates the whole stack and returns the largest element.

3Hint 3Explore hint

With up to 10⁵ queries and a stack of up to 10⁵ elements, scanning per query is O(n²) — too slow and it ignores the O(1) requirement.

A · Core idea

Keep a single stack. Push and pop normally. For a max query, walk every element and return the largest.

Why it's the obvious first cut. Push and pop are the native stack operations and need nothing extra. The maximum is derivable from the contents, so scanning answers it correctly.

Why it fails the bar. The problem explicitly wants O(1) max queries. A scan is O(n) per query; with q and n both up to 10⁵ that's up to 10¹⁰ operations and a timeout. It's correct but unacceptably slow — useful only to frame why we precompute the running max.

B · Visual dry run

Interactive dry run

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

queries = ["1 4", "1 7", "3", "2", "3"]

Array state

scan

look at 4, then 7 → max 7

[0]

[1]

Current pointerResolved stateNot processed

Final result

7
4

C · Code with teaching comments

Reference implementation previewimport java.util.*; public List<Integer> maximumElement(String[] queries) { Deque<Integer> stack = new ArrayDeque<>(); List<Integer> out = new ArrayList<>();Explore the full code

solution.javaJava

Brute Force — Scan the Stack on Every Max Query — reference

3 teaching notes

1
import java.util.*;
2
 
3
public List<Integer> maximumElement(String[] queries) {
4
    Deque<Integer> stack = new ArrayDeque<>();
5
    List<Integer> out = new ArrayList<>();
6
    for (String q : queries) {
7
        if (q.charAt(0) == '1') {
8
            int x = Integer.parseInt(q.split(" ")[1]);
9
            // Type 1: push — O(1).
10
            stack.push(x);
11
        } else if (q.charAt(0) == '2') {
12
            // Type 2: pop — O(1).
13
            stack.pop();
14
        } else {
15
            int best = Integer.MIN_VALUE;
16
            // Type 3: scan the whole stack — O(n) per query, the bottleneck.
17
            for (int v : stack) {
18
                best = Math.max(best, v);
19
            }
20
            out.add(best);
21
        }
22
    }
23
    return out;
24
}

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

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

The maximum only ever changes at the top of the stack — a push can raise it, a pop can lower it. That locality means we don't need to rescan; we can remember the max at each depth as we build the stack.

ComplexityO(q·n) time, O(n) space — Push/pop are O(1), but each type-3 query scans up to n elements; q such queries give O(q·n) worst case.

E · Edge cases and pitfalls4single push then max — Scan of one element returns it correctly, but still the wrong complexity class.Explore edge cases

Edge cases handled

single push then maxScan of one element returns it correctly, but still the wrong complexity class.

Pitfalls

O(n) per max query violates the explicit O(1) requirement.
Risk of TLE for q, n up to 10⁵.
Easy to write but signals you missed the auxiliary-stack idea.

03.2

Approach 2 of 2 · Optimal

Auxiliary Max Stack (Optimal)

TimeO(1) per querySpaceO(n)

The answer they want. Describe the parallel stack invariant: its top is always the current maximum.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The max changes only at the top. What if, alongside the data, you also stored 'the maximum of everything at or below this position'?

2Hint 2Explore hint

Keep a second stack. On push x, push max(x, currentMax) onto it; on pop, pop it too. Its top is always the current max.

3Hint 3Explore hint

A max query is then just reading the top of the auxiliary stack — O(1), no scan.

A · Core idea

Maintain two stacks of equal height: the main stack of values, and a maxStack whose top is always the maximum of everything currently in the main stack.

The invariant. After every operation, maxStack.peek() equals the maximum of the main stack. We preserve it on each operation:

Push x: push x onto the main stack and push max(x, maxStack.peek()) onto maxStack. The new running max is either the old max or x, whichever is larger. When the stack was empty, the previous max is −∞, so we just push x.
Pop: pop both stacks. Removing the top value also removes the max-so-far that it introduced, restoring maxStack's top to the maximum of the remaining elements — which is exactly the value that was there before this element was pushed.
Max query: return maxStack.peek().

Why store `max(x, prevMax)` and not just `x`. The max stack at depth d must answer 'what is the largest value among the bottom d elements?'. Storing the running max at each depth makes that a single read. Storing raw values would force a scan, defeating the purpose.

Why popping both keeps it correct. The two stacks always have the same height and were filled in lockstep, so the element at depth d in maxStack corresponds to the prefix of depth d in the main stack. Popping both unwinds exactly one push, and the new top of maxStack is the max of the new (shorter) prefix.

Why it's O(1). Push, pop, and peek on a stack are all constant time, and we do a fixed number of them per query. No scanning, ever.

B · Visual dry run

Interactive dry run

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

queries = ["1 97", "2", "1 20", "2", "1 26", "1 20", "2", "3", "1 91", "3"]

Array state

push 26

main [26], max [26]

[0]

Current pointerResolved stateNot processed

Final result

26
91

C · Code with teaching comments

solution.javaJava

Auxiliary Max Stack (Optimal) — optimal

5 teaching notes

1
import java.util.*;
2
 
3
public List<Integer> maximumElement(String[] queries) {
4
    Deque<Integer> main = new ArrayDeque<>();
5
    Deque<Integer> maxStack = new ArrayDeque<>();
6
    List<Integer> out = new ArrayList<>();
7
    for (String q : queries) {
8
        if (q.charAt(0) == '1') {
9
            int x = Integer.parseInt(q.substring(2).trim());
10
            // Type 1: push the value onto the data stack.
11
            main.push(x);
12
            // Running max = max of x and the previous max (or x if empty).
13
            int curMax = maxStack.isEmpty() ? x : Math.max(x, maxStack.peek());
14
            // Keep both stacks the same height; max stack top is now the current max.
15
            maxStack.push(curMax);
16
        } else if (q.charAt(0) == '2') {
17
            main.pop();
18
            maxStack.pop();
19
        } else {
20
            // Type 3: the current max is just the top of the max stack — O(1).
21
            out.add(maxStack.peek());
22
        }
23
    }
24
    return out;
25
}

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

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

The auxiliary stack is a 'shadow aggregate' that records the running maximum at every depth. Because max is monotone as the stack grows, each level's answer is just max(value, levelBelow). The identical pattern with min solves Min Stack — recognise it as the canonical way to give a LIFO an O(1) extreme.

ComplexityO(1) per query time, O(n) space — Each query does a constant number of stack operations → O(1) per query. Two stacks of up to n elements → O(n) space.

E · Edge cases and pitfalls6push 5, push 5, max, pop, max — Max stack holds [5, 5]; after a pop it's [5] → both queries print 5.Explore edge cases

Edge cases handled

push 5, push 5, max, pop, maxMax stack holds [5, 5]; after a pop it's [5] → both queries print 5.
single push then maxMax stack holds [x]; query returns x in O(1).

Pitfalls

Pushing raw x onto the max stack instead of max(x, previousMax).
Popping only one stack, desynchronising the two heights.
Forgetting the empty-max-stack case on the first push (previous max is −∞).
Re-scanning the main stack for the max instead of reading the max stack's top.

Practice

Try the solution yourself

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

Editable code previewimport java.util.*; public List<Integer> maximumElement(String[] queries) { Deque<Integer> main = new ArrayDeque<>(); Deque<Integer> maxStack = new ArrayDeque<>();Explore the playground

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

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Pushing raw values onto the max stack

The max stack must answer 'max of everything at or below this depth'. Storing the raw value means the top reflects only the latest element, not the running maximum, so the max query is wrong after a smaller value is pushed on top of a larger one.

Explore the code comparison

Don't write this

main.push(x);
maxStack.push(x);            // wrong: loses the running max
// after push(26), push(20): maxStack top is 20, but the max is 26

Write this instead

main.push(x);
int curMax = maxStack.isEmpty() ? x : Math.max(x, maxStack.peek());
maxStack.push(curMax);

Popping only one stack

If you pop the data stack but not the max stack, the two heights diverge and the max stack's top no longer corresponds to the current contents, corrupting every subsequent max query.

Explore the code comparison

Don't write this

main.pop()
# forgot max_stack.pop() -> stacks now out of sync

Write this instead

main.pop()
max_stack.pop()

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Stack + parallel max-stack tracking the running maximum

Code pattern to memorize

push(x): main.push(x); maxStack.push(max(x, maxStack.peekOrNegInf()))
pop():    main.pop();  maxStack.pop()
getMax(): return maxStack.peek()

Rules to remember

1Push onto both stacks every time; the max stack stores max(x, previousMax), never just x.
2Pop from both stacks together so they stay the same height and stay in sync.
3The maximum is always maxStack.peek() — never rescan the main stack (that would be O(n)).
4When the stack is empty the 'previous max' is −∞ (or just push the first element directly).
5Don't try to 'remove the max' on pop by searching — the parallel stack already encodes the max at every depth.

Use this pattern when

A stack where you must query the max (or min) in O(1) alongside push/pop
Min Stack / Max Stack design questions
Streaming pushes/pops with frequent extreme-value queries
Any LIFO structure needing an O(1) aggregate that's monotone under push/pop

Choose another pattern when

You need the max of a sliding window over a queue → monotonic deque, not a max stack
Arbitrary-position deletes (not just pop) → a stack can't model that; use a heap or balanced BST
You need the k-th largest, not just the max → a heap or order-statistics structure

Interview takeaway

Pair the data stack with a same-height max stack whose top is the running maximum. Push and pop them together and the max is always one peek away. This 'shadow aggregate stack' trick is the standard answer to Min/Max Stack and shows up wherever a LIFO needs an O(1) extreme.

Continue

Transfer the pattern to another problem

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

Transferable patternAuxiliary 'shadow' stack that mirrors a running aggregate (max here, min for Min Stack). Push and pop both stacks in lockstep; the aggregate is always the auxiliary stack's top, giving O(1) queries on a LIFO.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Min Stack
Same idea with min: an auxiliary stack whose top is the running minimum.
Max Stack
Coming soon
Adds popMax(); needs a heap or doubly linked list since the max may be in the middle.
Sliding Window Maximum
Coming soon
Max over a moving window — monotonic deque rather than a max stack.

Same pattern

←

Largest Rectangle in Histogram

Continue · Next problem

Min Max Riddle

easyStack QueueFrequently asked

Maximum Element

Stack & Queue · 12 of 17 · 8 min

You have an empty stack. Process q queries, each of one of three types:

1 x — push the integer x onto the stack.
2 — pop the element on top of the stack.
3 — print the maximum element currently in the stack.

All type-3 queries must run in O(1). Print the answer to each type-3 query on its own line.

In plain English

Examples

Example 1

Input: queries = ["1 97", "2", "1 20", "2", "1 26", "1 20", "2", "3", "1 91", "3"]
Output: 26 91
Note: After the pops, the stack holds [26]; max = 26. Then push 91 → stack [26, 91]; max = 91.

Example 2

Input: queries = ["1 4", "1 7", "3", "2", "3"]
Output: 7 4
Note: Push 4, push 7 → max 7. Pop 7 → stack [4] → max 4.

Example 3

Input: queries = ["1 5", "1 5", "3", "2", "3"]
Output: 5 5
Note: Duplicates: max stays 5 after pushing two 5s and after popping one.

Constraints

1 ≤ q ≤ 10⁵
1 ≤ x ≤ 10⁹
Type 2 (pop) is only issued when the stack is non-empty
Type 3 (max) is only issued when the stack is non-empty
Each operation must be O(1)

Clarifying questions4First question: Can the max query happen on an empty stack?Explore questions

Q1.Can the max query happen on an empty stack?
No — the constraints guarantee type-3 (and type-2) queries only occur when the stack is non-empty, so we don't special-case emptiness for them.
Q2.Must each query be O(1), or is O(n) per query acceptable?
O(1) is required. With q up to 10⁵, an O(n) scan per max query risks O(n²) and a timeout.
Q3.Can values repeat?
Yes. The max stack handles duplicates naturally because it stores the running max, which simply stays the same across equal values.
Q4.Could I store the max only when it changes, to save space?
You could (an index/count-based variant), but the full parallel stack is simpler and still O(n) space — fine for these limits.

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 achieve O(1) max queries by maintaining an auxiliary stack of running maxima, instead of scanning the stack on every query.

Where candidates slip

Recomputing the max by scanning the whole stack on each query (O(n) per query → O(nq) total), or pushing the raw value onto the max stack instead of max(value, previousMax).

How to stand out

State the auxiliary-max-stack invariant (its top equals the current maximum), show push/pop keep both stacks the same height, and note this is the same idea as Min Stack.

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 — Scan the Stack on Every Max Query	`O(q·n)`	`O(n)`	Mention to motivate the optimal, then note the O(n) per query cost violates the O(1) requirement.	Read
2	Auxiliary Max Stack (Optimal)Optimal	`O(1) per query`	`O(n)`	The answer they want. Describe the parallel stack invariant: its top is always the current maximum.	Read

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 — Scan the Stack on Every Max Query

TimeO(q·n)SpaceO(n)

Mention to motivate the optimal, then note the O(n) per query cost violates the O(1) requirement.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Push and pop are trivially O(1) on a stack. The only hard part is the max query.

2Hint 2Explore hint

The simplest max query iterates the whole stack and returns the largest element.

3Hint 3Explore hint

With up to 10⁵ queries and a stack of up to 10⁵ elements, scanning per query is O(n²) — too slow and it ignores the O(1) requirement.

A · Core idea

Keep a single stack. Push and pop normally. For a max query, walk every element and return the largest.

Why it's the obvious first cut. Push and pop are the native stack operations and need nothing extra. The maximum is derivable from the contents, so scanning answers it correctly.

B · Visual dry run

Interactive dry run

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

queries = ["1 4", "1 7", "3", "2", "3"]

Array state

scan

look at 4, then 7 → max 7

[0]

[1]

Current pointerResolved stateNot processed

Final result

7
4

C · Code with teaching comments

solution.javaJava

Brute Force — Scan the Stack on Every Max Query — reference

3 teaching notes

1
import java.util.*;
2
 
3
public List<Integer> maximumElement(String[] queries) {
4
    Deque<Integer> stack = new ArrayDeque<>();
5
    List<Integer> out = new ArrayList<>();
6
    for (String q : queries) {
7
        if (q.charAt(0) == '1') {
8
            int x = Integer.parseInt(q.split(" ")[1]);
9
            // Type 1: push — O(1).
10
            stack.push(x);
11
        } else if (q.charAt(0) == '2') {
12
            // Type 2: pop — O(1).
13
            stack.pop();
14
        } else {
15
            int best = Integer.MIN_VALUE;
16
            // Type 3: scan the whole stack — O(n) per query, the bottleneck.
17
            for (int v : stack) {
18
                best = Math.max(best, v);
19
            }
20
            out.add(best);
21
        }
22
    }
23
    return out;
24
}

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

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

ComplexityO(q·n) time, O(n) space — Push/pop are O(1), but each type-3 query scans up to n elements; q such queries give O(q·n) worst case.

E · Edge cases and pitfalls4single push then max — Scan of one element returns it correctly, but still the wrong complexity class.Explore edge cases

Edge cases handled

single push then maxScan of one element returns it correctly, but still the wrong complexity class.

Pitfalls

O(n) per max query violates the explicit O(1) requirement.
Risk of TLE for q, n up to 10⁵.
Easy to write but signals you missed the auxiliary-stack idea.

03.2

Approach 2 of 2 · Optimal

Auxiliary Max Stack (Optimal)

TimeO(1) per querySpaceO(n)

The answer they want. Describe the parallel stack invariant: its top is always the current maximum.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The max changes only at the top. What if, alongside the data, you also stored 'the maximum of everything at or below this position'?

2Hint 2Explore hint

Keep a second stack. On push x, push max(x, currentMax) onto it; on pop, pop it too. Its top is always the current max.

3Hint 3Explore hint

A max query is then just reading the top of the auxiliary stack — O(1), no scan.

A · Core idea

Maintain two stacks of equal height: the main stack of values, and a maxStack whose top is always the maximum of everything currently in the main stack.

The invariant. After every operation, maxStack.peek() equals the maximum of the main stack. We preserve it on each operation:

Push x: push x onto the main stack and push max(x, maxStack.peek()) onto maxStack. The new running max is either the old max or x, whichever is larger. When the stack was empty, the previous max is −∞, so we just push x.
Pop: pop both stacks. Removing the top value also removes the max-so-far that it introduced, restoring maxStack's top to the maximum of the remaining elements — which is exactly the value that was there before this element was pushed.
Max query: return maxStack.peek().

Why it's O(1). Push, pop, and peek on a stack are all constant time, and we do a fixed number of them per query. No scanning, ever.

B · Visual dry run

Interactive dry run

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

queries = ["1 97", "2", "1 20", "2", "1 26", "1 20", "2", "3", "1 91", "3"]

Array state

push 26

main [26], max [26]

[0]

Current pointerResolved stateNot processed

Final result

26
91

C · Code with teaching comments

solution.javaJava

Auxiliary Max Stack (Optimal) — optimal

5 teaching notes

1
import java.util.*;
2
 
3
public List<Integer> maximumElement(String[] queries) {
4
    Deque<Integer> main = new ArrayDeque<>();
5
    Deque<Integer> maxStack = new ArrayDeque<>();
6
    List<Integer> out = new ArrayList<>();
7
    for (String q : queries) {
8
        if (q.charAt(0) == '1') {
9
            int x = Integer.parseInt(q.substring(2).trim());
10
            // Type 1: push the value onto the data stack.
11
            main.push(x);
12
            // Running max = max of x and the previous max (or x if empty).
13
            int curMax = maxStack.isEmpty() ? x : Math.max(x, maxStack.peek());
14
            // Keep both stacks the same height; max stack top is now the current max.
15
            maxStack.push(curMax);
16
        } else if (q.charAt(0) == '2') {
17
            main.pop();
18
            maxStack.pop();
19
        } else {
20
            // Type 3: the current max is just the top of the max stack — O(1).
21
            out.add(maxStack.peek());
22
        }
23
    }
24
    return out;
25
}

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

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

ComplexityO(1) per query time, O(n) space — Each query does a constant number of stack operations → O(1) per query. Two stacks of up to n elements → O(n) space.

E · Edge cases and pitfalls6push 5, push 5, max, pop, max — Max stack holds [5, 5]; after a pop it's [5] → both queries print 5.Explore edge cases

Edge cases handled

push 5, push 5, max, pop, maxMax stack holds [5, 5]; after a pop it's [5] → both queries print 5.
single push then maxMax stack holds [x]; query returns x in O(1).

Pitfalls

Pushing raw x onto the max stack instead of max(x, previousMax).
Popping only one stack, desynchronising the two heights.
Forgetting the empty-max-stack case on the first push (previous max is −∞).
Re-scanning the main stack for the max instead of reading the max stack's top.

Practice

Try the solution yourself

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

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

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Pushing raw values onto the max stack

Explore the code comparison

Don't write this

main.push(x);
maxStack.push(x);            // wrong: loses the running max
// after push(26), push(20): maxStack top is 20, but the max is 26

Write this instead

main.push(x);
int curMax = maxStack.isEmpty() ? x : Math.max(x, maxStack.peek());
maxStack.push(curMax);

Popping only one stack

If you pop the data stack but not the max stack, the two heights diverge and the max stack's top no longer corresponds to the current contents, corrupting every subsequent max query.

Explore the code comparison

Don't write this

main.pop()
# forgot max_stack.pop() -> stacks now out of sync

Write this instead

main.pop()
max_stack.pop()

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Stack + parallel max-stack tracking the running maximum

Code pattern to memorize

push(x): main.push(x); maxStack.push(max(x, maxStack.peekOrNegInf()))
pop():    main.pop();  maxStack.pop()
getMax(): return maxStack.peek()

Rules to remember

1Push onto both stacks every time; the max stack stores max(x, previousMax), never just x.
2Pop from both stacks together so they stay the same height and stay in sync.
3The maximum is always maxStack.peek() — never rescan the main stack (that would be O(n)).
4When the stack is empty the 'previous max' is −∞ (or just push the first element directly).
5Don't try to 'remove the max' on pop by searching — the parallel stack already encodes the max at every depth.

Use this pattern when

A stack where you must query the max (or min) in O(1) alongside push/pop
Min Stack / Max Stack design questions
Streaming pushes/pops with frequent extreme-value queries
Any LIFO structure needing an O(1) aggregate that's monotone under push/pop

Choose another pattern when

You need the max of a sliding window over a queue → monotonic deque, not a max stack
Arbitrary-position deletes (not just pop) → a stack can't model that; use a heap or balanced BST
You need the k-th largest, not just the max → a heap or order-statistics structure

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

Min Stack
Same idea with min: an auxiliary stack whose top is the running minimum.
Max Stack
Coming soon
Adds popMax(); needs a heap or doubly linked list since the max may be in the middle.
Sliding Window Maximum
Coming soon
Max over a moving window — monotonic deque rather than a max stack.

Same pattern

←

Largest Rectangle in Histogram

Continue · Next problem

Min Max Riddle