# 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.
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
Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2] Output: false Explanation: 1 cannot be popped before 2.
Approach 1: simulate with a stack --
O(N) time and space.
# Code (Python)
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++)