065. Validate Stack Push/Pop Sequences

Why this mechanism works

Whenever the current top equals the next required output, popping it immediately cannot hurt: leaving it would only block access to values beneath it, and pushing more values is unnecessary for producing that required output. Simulate this forced opportunity after every push.

State and boundaries

j is the next required pop index. stack contains values pushed but not yet matched to the output sequence.

Protocol

1. Push the next input value.
2. While top equals popped[j], pop and advance j.
3. Continue with the next push.
4. Accept only if every requested output was matched.

Visualization

push 1,2,3,4; need 4 -> pop
next need 5 -> push 5, pop
then 3,2,1 can unwind

Python implementation

def valid_stack_sequences(pushed, popped):
    if len(pushed) != len(popped):
        return False
    stack = []
    j = 0
    for value in pushed:
        stack.append(value)
        while stack and j < len(popped) and stack[-1] == popped[j]:
            stack.pop()
            j += 1
    return j == len(popped)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 valid_stack_sequences: if len(pushed) != len(popped):
pushed=[1, 2, 3, 4, 5]; popped=[4, 5, 3, 2, 1]

L4 valid_stack_sequences: stack = []
pushed=[1, 2, 3, 4, 5]; popped=[4, 5, 3, 2, 1]; stack=[]

L5 valid_stack_sequences: j = 0
pushed=[1, 2, 3, 4, 5]; popped=[4, 5, 3, 2, 1]; stack=[]; j=0

L6 valid_stack_sequences: for value in pushed:
pushed=[1, 2, 3, 4, 5]; popped=[4, 5, 3, 2, 1]; stack=[]; j=0; value=1

L7 valid_stack_sequences: stack.append(value)
pushed=[1, 2, 3, 4, 5]; popped=[4, 5, 3, 2, 1]; stack=[1]; j=0; value=1

L6 valid_stack_sequences: for value in pushed:
pushed=[1, 2, 3, 4, 5]; popped=[4, 5, 3, 2, 1]; stack=[1]; j=0; value=2

L7 valid_stack_sequences: stack.append(value)
pushed=[1, 2, 3, 4, 5]; popped=[4, 5, 3, 2, 1]; stack=[1, 2]; j=0; value=2

L6 valid_stack_sequences: for value in pushed:
pushed=[1, 2, 3, 4, 5]; popped=[4, 5, 3, 2, 1]; stack=[1, 2]; j=0; value=3

... 11 intermediate state changes omitted ...

L9 valid_stack_sequences: stack.pop()
pushed=[1, 2, 3, 4, 5]; popped=[4, 5, 3, 2, 1]; stack=[1]; j=3; value=5

L10 valid_stack_sequences: j += 1
pushed=[1, 2, 3, 4, 5]; popped=[4, 5, 3, 2, 1]; stack=[1]; j=4; value=5

L9 valid_stack_sequences: stack.pop()
pushed=[1, 2, 3, 4, 5]; popped=[4, 5, 3, 2, 1]; stack=[]; j=4; value=5

L10 valid_stack_sequences: j += 1
pushed=[1, 2, 3, 4, 5]; popped=[4, 5, 3, 2, 1]; stack=[]; j=5; value=5

L2 valid_stack_sequences: if len(pushed) != len(popped):
pushed=[1, 2, 3, 4, 5]; popped=[4, 3, 5, 1, 2]

L4 valid_stack_sequences: stack = []
pushed=[1, 2, 3, 4, 5]; popped=[4, 3, 5, 1, 2]; stack=[]

L5 valid_stack_sequences: j = 0
pushed=[1, 2, 3, 4, 5]; popped=[4, 3, 5, 1, 2]; stack=[]; j=0

L6 valid_stack_sequences: for value in pushed:
pushed=[1, 2, 3, 4, 5]; popped=[4, 3, 5, 1, 2]; stack=[]; j=0; value=1

L7 valid_stack_sequences: stack.append(value)
pushed=[1, 2, 3, 4, 5]; popped=[4, 3, 5, 1, 2]; stack=[1]; j=0; value=1

L6 valid_stack_sequences: for value in pushed:
pushed=[1, 2, 3, 4, 5]; popped=[4, 3, 5, 1, 2]; stack=[1]; j=0; value=2

L7 valid_stack_sequences: stack.append(value)
pushed=[1, 2, 3, 4, 5]; popped=[4, 3, 5, 1, 2]; stack=[1, 2]; j=0; value=2

L6 valid_stack_sequences: for value in pushed:
pushed=[1, 2, 3, 4, 5]; popped=[4, 3, 5, 1, 2]; stack=[1, 2]; j=0; value=3

... 7 intermediate state changes omitted ...

L6 valid_stack_sequences: for value in pushed:
pushed=[1, 2, 3, 4, 5]; popped=[4, 3, 5, 1, 2]; stack=[1, 2]; j=2; value=5

L7 valid_stack_sequences: stack.append(value)
pushed=[1, 2, 3, 4, 5]; popped=[4, 3, 5, 1, 2]; stack=[1, 2, 5]; j=2; value=5

L9 valid_stack_sequences: stack.pop()
pushed=[1, 2, 3, 4, 5]; popped=[4, 3, 5, 1, 2]; stack=[1, 2]; j=2; value=5

L10 valid_stack_sequences: j += 1
pushed=[1, 2, 3, 4, 5]; popped=[4, 3, 5, 1, 2]; stack=[1, 2]; j=3; value=5

Why the solution is correct

Every simulated operation is legal. The next requested value cannot be popped unless it is on top; when it is, taking it cannot invalidate a later operation. Thus this greedy simulation succeeds exactly when the required order is achievable.

Time and space

O(n) time and O(n) space; each value is pushed and popped at most once.

Common mistakes

A single pop check can miss a whole newly exposed chain. Comparing unordered value sets does not validate stack order.

Reasoning card

Transfer exercise

Return one valid push/pop operation sequence as a witness, rather than only a Boolean result.