Decide if a pop sequence is valid
Updated
Given push order 1..n (or a given push sequence), a pop sequence is valid iff it could come from a stack: never pop a value that is not the current top, never pop before it has been pushed.
What to focus on
Simulate: iterate the desired pops, pushing from the unused prefix until the top matches or you cannot. If the stack top never matches the next needed pop, invalid.
Worked examples
valid reverse
pushes 4,1,9, pops 9,1,4- each needed value is top on time
Result: valid
valid mixed
pushes 4,1,9, pops 1,9,4- push 4,1 pop 1, push 9 pop 9, pop 4
Result: valid
invalid
pushes 4,1,9, pops 9,4,1- push 4,1,9, pop 9
- top is 1, need 4 next
- 1 blocks 4
Result: invalid
Try it
Write validPops(pushes, pops). pushes is the push order. pops is the proposed pop order. Simulate with a stack. Return valid only if each needed pop is the current top after pushing from the unused prefix. For pushes 4,1,9: 9,1,4 is valid; 1,9,4 is valid; 9,4,1 is invalid because after popping 9, top is 1 and you cannot pop 4 next.
Push order is the full sequence 4,1,9. Each value is popped at most once. Validity is the skill. Invalid order is in scope.