leetcode 946. Validate Stack Sequences (Python)

05 Jul 2020 Leetcode Stack

946. Validate Stack Sequences (Python)

Stack.

Description

Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Sample I/O

Example 1

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Note

  1. 0 <= pushed.length == popped.length <= 1000
  2. 0 <= pushed[i], popped[i] < 1000
  3. pushed is a permutation of popped.
  4. pushed and popped have distinct values.

Methodology

We need a stack to store temperoray value. Iterate the pushed list and append the value into stack if the top value of stack is equal to the popped[index] value then pop the top from stack and update the index. After iteration, if the stack is empty we know all values are operated and return true

    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        index = 0
        for x in pushed:
            stack.append(x)
            while stack and stack[-1] == popped[index]:
                stack.pop()
                index += 1
        return not stack

BigO

We iterate the list once so the total cost will be O(n)

Search

    Table of Contents