LeetCode 946 · Stack

Validate Stack Sequences, explained with a picture

Could the plates come off in this order?.

Stack
▶ Watch it step by step

The problem

Given the order plates were pushed onto a stack and a claimed order they were popped, decide whether that pop order is possible.

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

Picture it

Picture a waiter stacking plates. We replay the pushes; after each push, while the top plate is the next one that is supposed to come off, we pop it. If every plate gets popped in the claimed order, it was possible.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Simulate with a stack. O(n).

Python solution

def validate(pushed, popped):
    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)

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.