Stack With O(1) Access to Its Current Minimum
Solve this Problempush, pop, and top, plus a getMin operation that returns the smallest element currently on the stack — and make every one of those four operations run in O(1) time.
The trick is to never actually compute the minimum on demand. A second, parallel stack tracks it incrementally: every time a value is pushed, the min-stack also gets a push — either the new value itself (if it's smaller than or equal to the current minimum) or a repeat of the current minimum (if the new value is bigger and doesn't change anything). Every pop removes from both stacks together, so the min-stack's top is automatically correct for whatever remains. getMin then becomes nothing more than reading the min-stack's top — the minimum was already known the instant it was needed, because it was maintained the whole time, not searched for.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ ops.length ≤ 20 - ◆
ops[i] is one of "push", "pop", "top", "getMin"; args[i] is the value to push (0 for every other operation, unused) - ◆
"pop", "top", and "getMin" on an empty stack each return -1
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Scan the Whole Stack for Every getMin
BruteUse a plain stack for push, pop, and top — all O(1). For getMin, there's no shortcut: scan every element currently on the stack and track the smallest one seen. This is correct and simple, but a getMin call costs O(n), and a sequence with many getMin calls pays that cost every single time, even when nothing has changed since the last call.
O(1) push/pop/top, O(n) getMinO(n)1class Solution {
2 public int[] stackOpsMin(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 {
14 if (stack.isEmpty()) {
15 results.add(-1);
16 } else {
17 int min = stack.get(0);
18 for (int v : stack) min = Math.min(min, v);
19 results.add(min);
20 }
21 }
22 }
23 int[] output = new int[results.size()];
24 for (int i = 0; i < results.size(); i++) output[i] = results.get(i);
25 return output;
26 }
27}Optimal — Parallel Running-Minimum Stack
OptimalKeep a second stack alongside the main one, where each position stores "the minimum of everything at or below this depth" at the moment it was pushed. When pushing a new value, compare it to whatever's currently on top of the min-stack and push the smaller of the two (so the min-stack's top is always correct for the current state). When popping, pop both stacks together, so the min-stack's top instantly reflects what the minimum becomes once the value is removed. getMin is then just reading the top of the min-stack — no scanning, ever.
O(1) for every operationO(n)1class Solution {
2 public int[] stackOpsMin(String[] ops, int[] args) {
3 Deque<Integer> stack = new ArrayDeque<>();
4 Deque<Integer> minStack = 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 if (minStack.isEmpty() || v <= minStack.peek()) minStack.push(v);
12 else minStack.push(minStack.peek());
13 } else if (op.equals("pop")) {
14 if (stack.isEmpty()) { results.add(-1); }
15 else { results.add(stack.pop()); minStack.pop(); }
16 } else if (op.equals("top")) {
17 results.add(stack.isEmpty() ? -1 : stack.peek());
18 } else {
19 results.add(minStack.isEmpty() ? -1 : minStack.peek());
20 }
21 }
22 int[] output = new int[results.size()];
23 for (int i = 0; i < results.size(); i++) output[i] = results.get(i);
24 return output;
25 }
26}