Validate Stack Sequences — LeetCode 946 Python Solution

The problem

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

Example

Input

pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

Output

true

Explanation

We might do the following sequence:

Python solution

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stk = []
        i = 0
        for x in pushed:
            stk.append(x)
            while stk and stk[-1] == popped[i]:
                stk.pop()
                i += 1
        return i == len(popped)

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 946. Validate Stack Sequences is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems