#946

Validate Stack Sequences

pupil · 555 · lc medium +28 · verified · 70.2% accepted · 6,099 likes · top 79%

Description

Determine if integer arrays pushed and popped (each with distinct values) could represent the push order and pop order of some sequence of stack operations on an initially empty stack. Return true if possible, false otherwise.

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.

Code

1

2

3

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool: