DSA problem
Validate Stack Sequences
Given two integer arrays pushed and popped, each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.
In other words, we are asked: is there an interleaving of pushes (in the given push order) and pops such that the popped values come out exactly in the given pop order? Because every value is distinct, this is well-defined.
A brute-force search over all orderings is exponential. The clean greedy/simulation approach is to actually simulate a stack and decide, at each step, whether to push or to pop. The decisive observation is that whenever the top of our simulated stack matches the next expected pop, we MUST pop right now — if we waited and pushed more values on top, we'd never be able to surface the bottom value again.
The algorithm walks through pushed in order, pushing each value onto a simulated stack. After every push, repeatedly pop while the stack's top equals popped[j] (advancing j each time). At the end of the loop, if every popped value was matched (j == popped.length) the sequence is valid. Each value is pushed and popped at most once, so total work is O(n) time, O(n) space.
Examples
pushed = [1,2,3,4,5], popped = [4,5,3,2,1]truepushed = [1,2,3,4,5], popped = [4,3,5,1,2]falsepushed = [1,0], popped = [1,0]trueConstraints
- 1 <= pushed.length <= 1000
- 0 <= pushed[i] <= 1000
- All the elements of pushed are unique.
- popped.length == pushed.length
- popped is a permutation of pushed.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.