# 946. Validate Stack Sequences
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 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.
# Solution
Approach 1: simulate with a stack -- O(N)
time and space.
# Code (Python)
Approach 1:
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stack = []
stack_elements = set()
next_to_push = 0
for num in popped:
if num in stack_elements:
if stack[-1] != num:
return False
else:
stack_elements.remove(stack[-1])
stack.pop()
else:
while pushed[next_to_push] != num:
stack.append(pushed[next_to_push])
stack_elements.add(pushed[next_to_push])
next_to_push += 1
next_to_push += 1
return True
# Code (C++)
Approach 1:
Approach 2: