Validate Stack Sequences

Determine if a sequence of push/pop operations can produce a given output order.

stack simulation sequences

You are given two sequences of distinct integers: `pushed` and `popped`. The sequence `pushed` represents the order in which elements are pushed onto a stack (all pushes happen in that order, but you may pop at any time between pushes). The sequence `popped` represents a proposed order in which elements are popped from the stack. Write a function `validate_stack_sequences(pushed, popped)` that returns `True` if `popped` is a valid pop sequence for the stack given the push order `pushed`, and `False` otherwise.

Constraints:
- All integers in `pushed` are distinct.
- `len(pushed) == len(popped)`.
- The sequences are non-empty.
- The integers are not necessarily from 0 to n-1; they can be any integers.

You must simulate the stack operations to determine validity. You are allowed to pop from the stack only when the top element matches the next element in `popped`; otherwise, you must push the next element from `pushed` (if any). If you run out of pushes and the top does not match the next pop, the sequence is invalid.

Constraints

1 <= len(pushed) <= 1000
All elements in `pushed` and `popped` are distinct integers (each sequence has distinct values, but the two sequences may share the same set of values).
`len(pushed) == len(popped)`

Example

>>> validate_stack_sequences([1,2,3,4,5], [4,5,3,2,1])
True
>>> validate_stack_sequences([1,2,3,4,5], [4,3,5,1,2])
False
>>> validate_stack_sequences([2,1,0], [1,2,0])
True

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Simulate the process: use a list as a stack and two indices to track the next push and next pop.

While there is either a next push or the stack top matches the next pop, perform the appropriate operation.

At the end, the sequence is valid if you successfully pop every element in the popped order.

Think about when you must push: when the stack is empty or the top does not equal the next popped element.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.