Replay a Push-Pop Log
MediumStack
Problem
A warehouse stacks crates on a single pile. Crates arrive in the order pushed (all labels distinct). At any moment a worker may take the top crate off the pile.
Given the order popped in which crates left the pile, return true if it could have been produced by some interleaving of arrivals and removals, and false otherwise. Both arrays contain the same labels.
Example 1
- Input:
- pushed = [1, 2, 3, 4], popped = [2, 4, 3, 1]
- Output:
- true
push 1, push 2, pop 2, push 3, push 4, pop 4, pop 3, pop 1.
Example 2
- Input:
- pushed = [1, 2, 3], popped = [3, 1, 2]
- Output:
- false
After 3 leaves, 2 is on top of 1, so 1 cannot leave next.
Constraints
- 0 ≤ pushed.length ≤ 10^4
- popped is a permutation of pushed
- All labels are distinct
Hint
Show the first hint
Simulate the pile. When is it safe — and necessary — to pop?
Walkthrough
How to approach it
01Clarify before coding
- Are labels distinct? Yes, which makes the greedy choice unambiguous.
- Must all crates be pushed and popped? Yes, both arrays are permutations of each other.
02Brute force
Explore every interleaving of push and pop operations with backtracking and check whether any yields popped.
Cost: Exponential (Catalan-number many interleavings).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.