Stack Supporting Removal of Its Own Maximum Element
Solve this Problem
Design a stack that supports the usual
push, pop, and top, plus peekMax (return the current maximum without removing it) and popMax (remove and return the current maximum — which might not be on top of the stack at all, and could be buried anywhere below it).
peekMax reuses the same parallel-stack trick as tracking a running minimum: a second stack records the running maximum at every depth, so reading it is always O(1). popMax is the harder part, since the maximum being removed usually isn't the topmost element — everything above it has to move out of the way and then come back. The clean way to do that is a temporary buffer: pop elements (from both stacks together) into the buffer until the real maximum surfaces on top, discard it, then push the buffered elements back on in their original order, recomputing each one's max-stack entry as it's restored. Nothing above the maximum is lost or reordered — it's just temporarily set aside.
Test Case 1:
Input:ops = ["push","push","push","peekMax","popMax","top","peekMax"], args = [4,9,3,0,0,0,0]
Output:[9, 9, 3, 4]
Explanation:After pushing 4, 9, 3, the max is 9. popMax removes 9 specifically (even though it isn't on top), leaving [4,3] — top is now 3, and the max of what remains is 4.
Test Case 2:
Input:ops = ["push","push","push","push","popMax","popMax","top"], args = [2,7,7,5,0,0,0]
Output:[7, 7, 5]
Explanation:7 appears twice. The first popMax removes the topmost 7 (index 2), leaving [2,7,5]. The second popMax removes the remaining 7, leaving [2,5] — top is 5.
Test Case 3:
Input:ops = ["push","pop","peekMax","push","push","popMax","pop"], args = [6,0,0,1,8,0,0]
Output:[6, -1, 8, 1]
Explanation:Popping the only element leaves the stack empty, so peekMax returns -1. After pushing 1 then 8, popMax removes 8 (the max), leaving [1] — the final pop returns 1.
Constraints
- ◆
1 ≤ ops.length ≤ 20 - ◆
ops[i] is one of "push", "pop", "top", "peekMax", "popMax"; args[i] is the value to push (0 for every other operation, unused) - ◆
"pop", "top", "peekMax", and "popMax" on an empty stack each return -1 - ◆
If the maximum value appears more than once, popMax removes the topmost (most recently pushed) occurrence
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Scan for the Maximum on Every Query
BruteUse a plain stack for push, pop, and top. For peekMax, scan every element to find the largest. For popMax, scan to find the largest, then scan again (from the top down) to find its topmost occurrence, and remove that one element by shifting everything above it down by one slot. Correct, but both max-related operations pay a full O(n) cost every time they're called.
Time
O(1) push/pop/top, O(n) peekMax/popMaxSpace
O(n)Java
1class Solution {
2 public int[] stackOpsMax(String[] ops, int[] args) {
3 List<Integer> stack = new ArrayList<>();
4 List<Integer> results = new ArrayList<>();
5 for (int i = 0; i < ops.length; i++) {
6 String op = ops[i];
7 if (op.equals("push")) {
8 stack.add(args[i]);
9 } else if (op.equals("pop")) {
10 results.add(stack.isEmpty() ? -1 : stack.remove(stack.size() - 1));
11 } else if (op.equals("top")) {
12 results.add(stack.isEmpty() ? -1 : stack.get(stack.size() - 1));
13 } else if (op.equals("peekMax")) {
14 if (stack.isEmpty()) { results.add(-1); }
15 else {
16 int mx = stack.get(0);
17 for (int v : stack) mx = Math.max(mx, v);
18 results.add(mx);
19 }
20 } else {
21 if (stack.isEmpty()) { results.add(-1); }
22 else {
23 int mx = stack.get(0);
24 for (int v : stack) mx = Math.max(mx, v);
25 int idx = stack.lastIndexOf(mx);
26 stack.remove(idx);
27 results.add(mx);
28 }
29 }
30 }
31 int[] output = new int[results.size()];
32 for (int i = 0; i < results.size(); i++) output[i] = results.get(i);
33 return output;
34 }
35}Optimal — Parallel Max Stack With a Restore Buffer
OptimalKeep a second stack tracking the running maximum, exactly like the min-stack technique — every push records "the max of everything at or below this point," and peekMax is just an O(1) read of its top. popMax needs more care, since the maximum isn't always on top: pop elements off both stacks into a temporary buffer until the real top matches the known maximum, discard that one matching element from both stacks, then push everything from the buffer back on (in the same relative order), rebuilding the max-stack entries as they go. push, pop, top, and peekMax stay O(1); popMax costs O(n) only in the worst case (when the maximum is buried at the bottom), but never touches elements it doesn't have to relocate.
Time
O(1) push/pop/top/peekMax; O(n) worst case popMaxSpace
O(n)Java
1class Solution {
2 public int[] stackOpsMax(String[] ops, int[] args) {
3 Deque<Integer> stack = new ArrayDeque<>();
4 Deque<Integer> maxStack = new ArrayDeque<>();
5 List<Integer> results = new ArrayList<>();
6 for (int i = 0; i < ops.length; i++) {
7 String op = ops[i];
8 if (op.equals("push")) {
9 int v = args[i];
10 stack.push(v);
11 maxStack.push(maxStack.isEmpty() ? v : Math.max(v, maxStack.peek()));
12 } else if (op.equals("pop")) {
13 if (stack.isEmpty()) { results.add(-1); }
14 else { results.add(stack.pop()); maxStack.pop(); }
15 } else if (op.equals("top")) {
16 results.add(stack.isEmpty() ? -1 : stack.peek());
17 } else if (op.equals("peekMax")) {
18 results.add(maxStack.isEmpty() ? -1 : maxStack.peek());
19 } else {
20 if (stack.isEmpty()) { results.add(-1); }
21 else {
22 int mx = maxStack.peek();
23 List<Integer> buffer = new ArrayList<>();
24 while (stack.peek() != mx) {
25 buffer.add(stack.pop());
26 maxStack.pop();
27 }
28 stack.pop();
29 maxStack.pop();
30 for (int j = buffer.size() - 1; j >= 0; j--) {
31 int v = buffer.get(j);
32 stack.push(v);
33 maxStack.push(maxStack.isEmpty() ? v : Math.max(v, maxStack.peek()));
34 }
35 results.add(mx);
36 }
37 }
38 }
39 int[] output = new int[results.size()];
40 for (int i = 0; i < results.size(); i++) output[i] = results.get(i);
41 return output;
42 }
43}