#946

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Validate Stack Sequences

Determine if a sequence of push and pop operations can produce the given popped array using a stack-based state approach.

array stack simulation

Problem Statement

Given two arrays of distinct integers, pushed and popped, determine if the popped array can result from a sequence of push and pop operations on an initially empty stack. Elements must be pushed in the order they appear in the pushed array, and you may pop from the stack at any time if the top matches the next element in popped.

Return true if it is possible to perform these operations so that the popped sequence is exactly produced; otherwise, return false. For example, pushed = [1,2,3,4,5] and popped = [4,5,3,2,1] should return true, while pushed = [1,2,3,4,5] and popped = [4,3,5,1,2] should return false because 1 cannot be popped before 2.

Examples

Example 1

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

Output: true

We might do the following sequence: push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

Output: false

1 cannot be popped before 2.

Constraints

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.

Solution Approach

Simulate Stack with Two Pointers

Use a stack to push elements from the pushed array. Maintain a pointer on the popped array. Whenever the top of the stack matches popped[current], pop it and move the pointer. Continue until all elements are processed.

Validate Sequence

After pushing all elements from pushed, if the stack becomes empty exactly when the popped pointer reaches the end, the sequence is valid. Otherwise, return false. This approach captures the stack-based state management required for this problem.

Edge Case Handling

Ensure that pushed and popped arrays are of the same length and contain the same unique elements. Avoid skipping checks for top-of-stack matches or incorrectly assuming sequences are always valid when duplicates or missing elements exist.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each element is pushed and popped at most once. Space complexity is O(n) to store the stack in the worst case, proportional to the length of the pushed array.

What Interviewers Usually Probe

Looking for clear stack simulation and pointer usage.
Expect recognition that element order in pushed matters.
Watch for correct handling of stack top matching popped elements.

Common Pitfalls or Variants

Common pitfalls

Attempting to pop elements in an order not allowed by the stack.
Forgetting to check stack top against the current popped element repeatedly.
Assuming sequences are valid without simulating push and pop accurately.

Follow-up variants

Sequences where pushed and popped include duplicate values.
Larger arrays requiring optimized in-place simulation.
Generating the valid popped sequence given a random pushed array.

FAQ

What is the main strategy for Validate Stack Sequences?

Simulate a stack pushing elements from pushed and popping when the top matches the next popped element.

Can I use recursion instead of an explicit stack?

Yes, recursion can mimic the stack behavior but may increase call stack usage; the iterative stack is simpler and safer.

What if pushed and popped arrays have different lengths?

The sequence is invalid; they must have the same length and contain the same unique elements.

How do I handle an empty pushed array?

An empty pushed array is valid only if the popped array is also empty, otherwise return false.

Why does the stack top check fail in some sequences?

The stack top check fails when a pop operation is attempted before the corresponding element is pushed, violating stack order.

terminal

Solution

Solution 1: Stack Simulation

We iterate through the $\textit{pushed}$ array. For the current element $x$ being iterated, we push it into the stack $\textit{stk}$. Then, we check if the top element of the stack is equal to the next element to be popped in the $\textit{popped}$ array. If they are equal, we pop the top element from the stack and increment the index $i$ of the next element to be popped in the $\textit{popped}$ array. Finally, if all elements can be popped in the order specified by the $\textit{popped}$ array, return $\textit{true}$; otherwise, return $\textit{false}$.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stk = []
        i = 0
        for x in pushed:
            stk.append(x)
            while stk and stk[-1] == popped[i]:
                stk.pop()
                i += 1
        return i == len(popped)

Continue Practicing

#735 asteroid collision #682 baseball game #1441 build an array with stack operations