Validate Stack Sequences — Simulate Push/Pop (LeetCode 946)

Validate Stack Sequences (LeetCode 946) gives you two sequences — pushed and popped — and asks whether the popped sequence could result from a series of push and pop operations on an initially empty stack, given that elements are pushed in the order of pushed.

The Problem

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

Push 1, Push 2, Push 3, Push 4, Pop 4, Push 5, Pop 5, Pop 3, Pop 2, Pop 1

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

After popping 4, 3 and pushing 5, popping 5 gives [1, 2] on stack.
We need to pop 1 next, but 2 is on top. Invalid!

Approach: Greedy Simulation

The idea is simple: simulate the stack operations.

1. Push elements from pushed one by one
2. After each push, greedily pop as many elements as possible that match the front of popped
3. If we consume all of popped, the sequence is valid

def validateStackSequences(pushed, popped):
    """
    Simulate push/pop operations greedily.
    Time: O(n), Space: O(n)
    """
    stack = []
    j = 0  # pointer into popped

    for val in pushed:
        stack.append(val)

        # Greedily pop whenever the top matches
        while stack and j < len(popped) and stack[-1] == popped[j]:
            stack.pop()
            j += 1

    return j == len(popped)

That is the entire solution. Let us trace through it carefully.

Step-by-Step Trace: Valid Case

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

Step 1: push 1 → stack = [1], j=0, popped[0]=4, 1≠4 → no pop
Step 2: push 2 → stack = [1,2], j=0, 2≠4 → no pop
Step 3: push 3 → stack = [1,2,3], j=0, 3≠4 → no pop
Step 4: push 4 → stack = [1,2,3,4], j=0, 4==4 → pop!
        stack = [1,2,3], j=1, popped[1]=5, 3≠5 → stop
Step 5: push 5 → stack = [1,2,3,5], j=1, 5==5 → pop!
        stack = [1,2,3], j=2, 3==3 → pop!
        stack = [1,2], j=3, 2==2 → pop!
        stack = [1], j=4, 1==1 → pop!
        stack = [], j=5 → stop

j == 5 == len(popped) → TRUE

Step-by-Step Trace: Invalid Case

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

Step 1: push 1 → stack = [1], j=0, 1≠4 → no pop
Step 2: push 2 → stack = [1,2], j=0, 2≠4 → no pop
Step 3: push 3 → stack = [1,2,3], j=0, 3≠4 → no pop
Step 4: push 4 → stack = [1,2,3,4], j=0, 4==4 → pop!
        stack = [1,2,3], j=1, 3==3 → pop!
        stack = [1,2], j=2, 2≠5 → stop
Step 5: push 5 → stack = [1,2,5], j=2, 5==5 → pop!
        stack = [1,2], j=3, 2≠1 → stop

All pushed, j=3 ≠ 5 → FALSE

Stack has [1, 2] left. We need to pop 1 but 2 is on top.

Why Greedy Works

The key insight: we should always pop as soon as we can. Delaying a pop never helps — if the top of the stack matches the next element in popped, we must pop it now because:

1. If we delay and push more elements, those new elements will be on top
2. We would still need to pop the matching element eventually
3. But it will be buried under the new elements, possibly in the wrong order

So the greedy strategy (pop whenever possible) is both necessary and sufficient.

Space-Optimized Version

We can use the pushed array itself as the stack, avoiding extra space:

def validateStackSequences_inplace(pushed, popped):
    """
    Use pushed array as the stack — O(1) extra space.
    Time: O(n), Space: O(1)
    """
    top = 0  # stack pointer within pushed
    j = 0    # pointer into popped

    for val in pushed:
        pushed[top] = val
        top += 1

        while top > 0 and j < len(popped) and pushed[top-1] == popped[j]:
            top -= 1
            j += 1

    return j == len(popped)

This treats pushed[0:top] as the stack. Each push writes to pushed[top], and pops just decrement top.

Complexity Analysis

Approach	Time	Space
Stack simulation	O(n)	O(n)
In-place	O(n)	O(1)

Each element is pushed once and popped at most once, giving a total of 2n operations = O(n).

Edge Cases

# Empty arrays
assert validateStackSequences([], []) == True

# Single element
assert validateStackSequences([1], [1]) == True

# Already sorted (push all, then pop all)
assert validateStackSequences([1,2,3], [3,2,1]) == True

# Pop in push order (pop each immediately after push)
assert validateStackSequences([1,2,3], [1,2,3]) == True

# Impossible: first pop is not in pushed
# (This cannot happen per constraints — both are permutations)

# Large case with alternating push/pop
pushed = list(range(1, 1001))
popped = list(range(1, 1001))  # pop immediately
assert validateStackSequences(pushed, popped) == True

When to Use This Pattern

Use stack simulation when:

• You need to verify if a sequence of operations is valid for a stack or queue
• The problem involves simulating a process with push/pop semantics
• You see “validate” or “check if possible” with ordered operations
• The greedy approach of “process as early as possible” applies

Common Mistakes

1. Forgetting the while loop — you might pop multiple elements in a row, not just one
2. Not checking bounds on both stack (non-empty) and j (within popped range)
3. Checking stack == [] at the end instead of j == len(popped) — both work, but the j check is cleaner

Related Problems

Problem	Key Difference
Asteroid Collision (LC 735)	Stack simulation with collision rules
Baseball Game (LC 682)	Stack simulation with scoring rules
Decode String (LC 394)	Stack for nested bracket processing
Sort a Stack	Validate vs construct the output
Design Stack with Increment (LC 1381)	Design variant with lazy propagation

Key Takeaways

• Validate Stack Sequences is a greedy simulation problem
• Push elements one by one; pop greedily whenever the stack top matches
• The greedy strategy is optimal — delaying a pop never helps
• The in-place variant uses O(1) extra space by reusing the input array
• This pattern (simulate and greedily process) applies to many validation problems