Validate Stack Sequences: Greedy Stack Simulation

You are 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, and false otherwise.

This is LeetCode 946: Validate Stack Sequences, a medium problem that tests whether you can simulate stack operations efficiently. The core idea is simple: push elements one at a time and greedily pop whenever the stack top matches the next expected pop value.

Why this problem matters

Validate Stack Sequences is one of those problems that looks tricky at first but becomes clean once you see the greedy simulation pattern. It shows up in interviews as a test of whether you can think about stack operations without getting lost in the details.

More importantly, it teaches you a reusable technique: when you need to verify that a sequence of operations is valid, simulate the process step by step and check the constraints as you go. This same approach applies to validating parentheses, checking task schedules, and verifying serialization formats.

The brute force approach

A brute force approach would try every possible ordering of push and pop operations. At each step, you could either push the next element from pushed or pop from the stack (if it is not empty). You would explore all possible interleavings and check if any of them produce the popped sequence.

This is exponential. With n elements, there are roughly 2^n possible orderings to check. For n = 1000, that is completely impractical.

The good news is that you do not need to explore multiple paths. There is only one correct strategy, and it is greedy.

The key insight: greedy simulation

Why is greedy correct here? Because all values are distinct. If the stack top equals popped[j], the only way that value can ever leave the stack is by popping it now. If you push more elements on top of it first, those elements will need to be popped before you can reach it again, and by then popped[j] will have passed. Delaying a pop that matches can only cause problems, never solve them.

This means there is exactly one valid simulation path. You push elements in order, and you pop eagerly whenever the top matches. If the stack is empty at the end, the sequence is valid.

Walking through it step by step

Let's trace through pushed = [1, 2, 3, 4, 5] and popped = [4, 5, 3, 2, 1]. We maintain a simulation stack and a pointer j into the popped array.

Notice a few things:

• The pop pointer only moves forward. Each time we pop, j advances by one. It never goes backward.
• Step 4 is where the first match happens. After pushing 4, the top finally matches popped[0]. We pop immediately.
• Step 5 triggers a chain reaction. After pushing 5, the top matches popped[1]. We pop 5, then 3 matches popped[2], then 2 matches popped[3], then 1 matches popped[4]. The entire stack drains in one burst.
• Each element is pushed once and popped once. That is why the total work is O(n), even when a single step triggers multiple pops.

The simulation solution

def validateStackSequences(pushed, popped):
    stack = []
    j = 0
    for val in pushed:
        stack.append(val)
        while stack and stack[-1] == popped[j]:
            stack.pop()
            j += 1
    return len(stack) == 0

Four lines of logic. Here is what each piece does:

1. Initialize an empty stack and a pointer j = 0 into the popped array.
2. Walk through each value in pushed from left to right.
3. Push the current value onto the stack.
4. While the stack is not empty and the top equals popped[j]: pop and advance j.
5. After processing all elements, check if the stack is empty. If it is, every pop matched and the sequence is valid.

The while loop is the heart of the algorithm. It greedily pops as many elements as possible after each push. Across the entire run, each element enters the stack once and leaves at most once, so the total number of pop operations is at most n.

Complexity analysis

The O(n) time comes from the fact that the while loop does at most n pops total across all iterations of the for loop. Even though some iterations trigger multiple pops (like Step 5 in our walkthrough), the total is bounded by n because each element can only be popped once.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Stack simulation

The pattern of using an auxiliary stack to simulate a process step by step:

stack = []
for item in sequence:
    stack.append(item)
    while stack and should_pop(stack[-1]):
        stack.pop()

In Validate Stack Sequences, should_pop checks whether the top matches the next expected pop value. In Valid Parentheses, it checks whether the top is the matching open bracket. In Asteroid Collision, it checks whether the top asteroid should be destroyed. The skeleton is the same: push, then conditionally pop in a while loop.

2. Greedy eager popping

The pattern of making an irrevocable decision at the earliest possible moment:

pointer = 0
for item in sequence:
    process(item)
    while can_advance(pointer):
        advance(pointer)
        pointer += 1

In Validate Stack Sequences, the pointer tracks position in the popped array and advances every time a pop succeeds. In problems like Gas Station or Jump Game, a similar pointer or counter tracks progress and advances greedily. The key property is that delaying the advance is never beneficial.

Edge cases

Before submitting, make sure your solution handles these:

• Already sorted pops pushed = [1, 2, 3], popped = [1, 2, 3]: every element is popped immediately after being pushed. The stack never grows beyond size 1. Returns true.
• Reverse order pops pushed = [1, 2, 3], popped = [3, 2, 1]: nothing pops until all elements are pushed, then everything pops at once. Returns true.
• Invalid sequence pushed = [1, 2, 3], popped = [3, 1, 2]: after pushing all three and popping 3, the top is 2 but popped[1] is 1. The stack is not empty at the end. Returns false.
• Single element pushed = [1], popped = [1]: push 1, pop 1, stack is empty. Returns true.
• Two elements, invalid pushed = [1, 2], popped = [2, 1]: valid (push both, pop both). pushed = [1, 2], popped = [1, 2]: also valid (push 1, pop 1, push 2, pop 2).

The greedy simulation handles all of these without special-case logic.

Common mistakes

1. Not using a while loop for the pop check. After each push, you might need to pop multiple times in a row. Using an if instead of while misses the chain reaction (like Step 5 in our walkthrough where four pops happen consecutively).

2. Forgetting to check if stack before accessing stack[-1]. The while loop handles this with stack and ..., but if you restructure the code, an empty stack access will crash.

3. Comparing values instead of using the pop pointer. Some people try to search through the popped array for each value. You do not need to search. The pointer j always tells you which value should be popped next.

4. Trying to pop before pushing. The algorithm pushes first, then checks for pops. Reversing this order breaks the simulation because you might try to pop a value that has not been pushed yet.

From understanding to recall

You have read through the greedy simulation and it makes sense. Push elements, eagerly pop when the top matches, check if the stack is empty. Clean. But can you write it from scratch in an interview three weeks from now?

The details matter: remembering to use a while loop (not if), advancing j on each pop, and checking len(stack) == 0 at the end. These are small but critical, and they are easy to mix up under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the simulation loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "validate a sequence of operations" and the code flows out without hesitation.

Related posts

• Min Stack - Stack with auxiliary tracking
• Valid Parentheses - Stack-based validation of sequences
• Daily Temperatures - Monotonic stack pattern

CodeBricks breaks the validate stack sequences problem into its stack simulation and greedy popping building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a stack simulation question shows up in your interview, you do not think about it. You just write it.