Validate Stack Sequences
Medium · Stack & Strings · Array · Stack · Simulation
Problem
You are given two integer arrays pushed and popped, each holding the same distinct values. Starting from an empty stack, you push the values of pushed in order, and at any moment you may pop the top of the stack.
Return true if some interleaving of these pushes and pops removes the values in exactly the order given by popped, and false otherwise.
Examples
Input: pushed = [1,2,3,4], popped = [2,1,4,3] Output: true
Push 1, push 2, pop 2, pop 1, push 3, push 4, pop 4, pop 3.
Input: pushed = [1,2,3], popped = [3,1,2] Output: false
Once 3 is popped, 2 sits above 1, so 1 cannot come out next.
Input: pushed = [1,2,3,4,5], popped = [5,4,3,2,1] Output: true
Push everything, then pop everything.
Constraints
- 1 <= len(pushed) <= 1000
- 0 <= pushed[i] <= 1000
- All values of pushed are distinct
- len(popped) == len(pushed)
- popped is a permutation of pushed
Approaches
- Check the forbidden pattern — time O(n²), space O(n)
Follow-up
Because the values are distinct, the greedy simulation is not just one way but the only way: the pushes and pops are forced. The use cases return that forced sequence of operations, and the largest height the stack reaches.
Related problems
Start free on Cariara · Coding problems · System design studio
