Can this order happen
Given the order in which items were pushed and an order in which they were popped, decide whether some mix of pushes and pops could produce it. About 14 minutes.
Pop as soon as you can
Items 1 to 5 are pushed in that order. Could they be popped as 4, 5, 3, 2, 1? Simulate. Push items one by one. After each push, look at the top: if it is the next item that the popped order wants, pop it, and keep popping while the new top also matches.
There is no reason to wait. An item at the top that is wanted now can only get buried if you push more on it, and then it could not come out before them.
stack = [1, 2]
while stack and stack[-1] == 2:
stack.pop()Push 1, 2 and 3. The wanted first pop is 3 and it is on top, so pop it. Next wanted is 1. Stack: 1, 2.
The verdict
When all items have been pushed, nothing more can be pushed. Any items still on the stack must now come out top first. If they do not match the rest of the wanted order, the order is impossible.
So the answer is whether the pointer reached the end of the popped order, meaning every wanted item was popped. The two lists have the same distinct items.
all_popped = len(stack) == 0
Pushed 1, 2, 3. Wanted pops: 3, 1, 2. Is it possible?
- ANo
- BYes
- CIt depends on the push times
Show the answer
No. After 3 is popped, the stack is 1, 2 with 2 on top, so 2 must come out before 1.
Validate stack sequences
You are given two integer arrays pushed and popped, each with distinct values and the same length. Return true if they could be the sequence of pushes and pops of one empty stack, where items are pushed in the order of pushed and popped in the order of popped, and pops may be done at any time when the stack is not empty.
pushed = [1, 2, 3, 4, 5], popped = [4, 5, 3, 2, 1] → true
0 ≤ length ≤ 100,000 · distinct values · popped is a permutation of pushed