Stack Permutations Validity

Problem

Determine whether a sequence can be produced as a stack permutation of another sequence.

pushed is the order in which values are pushed and popped is the proposed pop order. Simulate with a stack: push each value, then pop while the top matches the next expected value.

Return True when the whole popped sequence is produced and the stack ends empty, otherwise False.

Hint

Greedily pop whenever the stack top equals the next value of popped; at the end the stack must be empty.

Test cases

case 1

in: [[1,2,3],[3,2,1]]

expected: true

case 2

in: [[1,2,3],[3,1,2]]

expected: false

case 3

in: [[1,2],[2,1]]

expected: true

case 4

in: [[],[]]

expected: true

case 5

in: [[1,2,3,4],[2,1,4,3]]

expected: true

Starter codePython

def valid_stack_permutations(pushed, popped):
    # Your code here
    pass

5 test cases · run your code against them in the editor