564. Validate Stack Sequences
You are given two integer arrays pushed and popped, each a permutation of the same set of distinct values.
Starting from an empty stack, the values of pushed must be pushed in the given order, but you may pop the stack at any moment in between. Return true if some sequence of pushes and pops could produce exactly popped as the order in which values leave the stack, and false otherwise.
Example 1:
Input: pushed = [1, 2, 3, 4, 5], popped = [4, 5, 3, 2, 1]
Output: true
Explanation: Push 1, 2, 3, 4 — pop 4 — push 5 — pop 5 — then pop 3, 2, 1. The pops come off in exactly the order 4, 5, 3, 2, 1.
Example 2:
Input: pushed = [1, 2, 3, 4, 5], popped = [4, 3, 5, 1, 2]
Output: false
Explanation: After popping 4, 3, and 5 the stack holds [1, 2] with 2 on top, so 2 must leave before 1 — the tail 1, 2 is impossible.
Constraints:
- 1 ≤ pushed.length ≤ 10⁵
- popped.length == pushed.length
- 0 ≤ pushed[i] ≤ 10⁹
- All values of pushed are distinct; popped is a permutation of pushed.
Hints:
You never have to guess. At any moment there is exactly one value that popped says must leave next — and it can only leave if it is sitting on top of the stack.
Simulate: push values from pushed one by one, and after each push greedily pop while the stack's top equals the next value popped expects. If everything drains, the sequence is valid.
Popping the moment the top matches is always safe: delaying a matching pop only buries the value deeper under later pushes.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: pushed = [1, 2, 3, 4, 5], popped = [4, 5, 3, 2, 1]
Expected output: true