Validate Stack Sequences
Given two arrays pushedpoppedpushedpopped
Example 1
Output: true
Explanation: push 1, 2, 3, 4, pop 4, push 5, pop 5, 3, 2, 1.
Example 2
Output: false
Explanation: 1 cannot be popped before 2, since 2 is above it.
How to Think About It
Step 1: Just simulate
Use a real stack. Push the values in order, and pop whenever the stack's top is the next value we need to pop.
Step 2: Popping as early as possible is always safe
If the top equals the next value in popped
Step 3: The verdict
After all pushes (each followed by as many pops as possible), the sequence is valid exactly when the stack is empty.
Walkthrough
Example 1, step by step:
| Pushed | Popped right after | Stack after | Next value to pop |
|---|---|---|---|
| 1, 2, 3 | [1, 2, 3] | 4 | |
| 4 | 4 | [1, 2, 3] | 5 |
| 5 | 5, 3, 2, 1 | [] | done |
For example 2, after popping 4, 3 and pushing and popping 5, the stack is [1, 2] with 2 on top, but the next value needed is 1. The stack is not empty at the end, so the answer is false.
Java Solution
nextpopped
import java.util.ArrayDeque;
import java.util.Deque;
public class ValidateStackSequences {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stack = new ArrayDeque<>();
int next = 0; // next value of popped to produce
for (int value : pushed) {
stack.push(value);
while (!stack.isEmpty() && stack.peek() == popped[next]) {
stack.pop(); // pop as soon as the top is the value we need
next++;
}
}
return stack.isEmpty();
}
}
The original implementation,
Complexity
- Time: O(n): each value is pushed and popped at most once.
- Space: O(n) for the stack.
Simulating the structure itself is often the simplest check, as in