LeetCode 946: Validate Stack Sequences

Problem Restatement

We are given two integer arrays:

pushed
popped

Both arrays contain the same distinct values.

pushed gives the order in which values are pushed onto an initially empty stack.

popped gives a possible order in which values are popped from the stack.

Return True if popped could be produced by valid stack operations. Otherwise, return False.

The official statement asks whether popped could result from a sequence of push and pop operations on an initially empty stack, using the values from pushed in order.

Input and Output

Function shape:

class Solution:
    def validateStackSequences(self, pushed: list[int], popped: list[int]) -> bool:
        ...

Examples

Example 1:

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

This is valid.

One possible operation sequence is:

push 1
push 2
push 3
push 4
pop 4
push 5
pop 5
pop 3
pop 2
pop 1

So the answer is:

True

Example 2:

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

We can pop 4, then 3, then 5.

But after that, the stack has:

1, 2

with 2 on top.

So 1 cannot be popped before 2.

Answer:

False

First Thought

We can directly simulate the stack.

The push order is fixed.

The only choice is when to pop.

So after every push, we should pop as many values as possible while the stack top matches the next required value in popped.

If the simulation can consume all values in popped, the sequence is valid.

Key Insight

A stack only allows popping the top value.

So at any point, if:

stack[-1] == popped[j]

then we should pop it immediately.

There is no benefit to waiting, because future pushes would only place more values above it and make it harder to pop now.

This greedy simulation is enough.

Algorithm

Initialize:

stack = []
j = 0

For each value x in pushed:

1. Push x onto the stack.
2. While the stack is not empty and the top equals popped[j]:
   • pop the stack
   • move j forward

At the end, return whether all popped values were matched:

j == len(popped)

Walkthrough

Use:

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

All values in popped were matched.

Return:

True

Correctness

The algorithm pushes values in exactly the order given by pushed, so it respects the required push order.

After each push, it pops while the stack top equals the next required value in popped. Each such pop is valid because the value is at the top of the stack.

If the next required popped value is not at the top, it cannot be popped at that moment. The only possible action is to push more values, which is exactly what the algorithm does.

Whenever the top value matches the next required popped value, popping immediately is safe. Delaying that pop would only allow more pushed values to be placed above it, but the same value must still be popped before the later values below it can be reached.

Therefore, the simulation never rejects a sequence that could be valid.

If the algorithm matches all values in popped, it has built a valid sequence of stack operations, so it returns True.

If it cannot match all values, then some required pop order conflicts with the stack top order. No valid sequence can produce popped, so it returns False.

Complexity

Let:

n = len(pushed)

Implementation

class Solution:
    def validateStackSequences(self, pushed: list[int], popped: list[int]) -> bool:
        stack = []
        j = 0

        for x in pushed:
            stack.append(x)

            while stack and stack[-1] == popped[j]:
                stack.pop()
                j += 1

        return j == len(popped)

Code Explanation

stack simulates the real stack:

stack = []

j points to the next value we need to pop:

j = 0

For every value in the push order, we push it:

stack.append(x)

Then we repeatedly pop while the top matches the required pop value:

while stack and stack[-1] == popped[j]:
    stack.pop()
    j += 1

At the end, if j reached the length of popped, every required pop was matched:

return j == len(popped)

Testing

def run_tests():
    s = Solution()

    assert s.validateStackSequences(
        [1, 2, 3, 4, 5],
        [4, 5, 3, 2, 1],
    ) is True

    assert s.validateStackSequences(
        [1, 2, 3, 4, 5],
        [4, 3, 5, 1, 2],
    ) is False

    assert s.validateStackSequences(
        [1],
        [1],
    ) is True

    assert s.validateStackSequences(
        [1, 2, 3],
        [1, 2, 3],
    ) is True

    assert s.validateStackSequences(
        [1, 2, 3],
        [3, 2, 1],
    ) is True

    print("all tests passed")

run_tests()