# Validate Stack Sequences

##### January 26, 2024

## Problem Statement #

Given two sequences `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, otherwise `false`

.

**Example**:

- Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1] Output: True Explanation: We can push 1, 2, 3, 4, and 5 and then pop them in the order [4,5,3,2,1].

## Solution Approach #

The solution involves simulating the push and pop operations on a stack.

### Algorithm Steps #

- Initialize an empty stack and a pointer for the
`popped`

sequence. - Iterate through each element in the
`pushed`

sequence: a. Push the element onto the stack. b. While the stack is not empty and the top of the stack equals the current element at the`popped`

pointer, pop from the stack and move the pointer. - After the iteration, if the stack is empty, return
`true`

; otherwise, return`false`

.

### Code (Python) #

```
def validateStackSequences(pushed, popped):
stack = []
pop_index = 0
for num in pushed:
stack.append(num)
while stack and stack[-1] == popped[pop_index]:
stack.pop()
pop_index += 1
return not stack
# Test the function
print(validateStackSequences([1,2,3,4,5], [4,5,3,2,1])) # Output: True
```

### Time Complexity #

O(n), where n is the number of elements in `pushed`

and `popped`

. Each element is processed once.

### Space Complexity #

O(n), for the stack used in the simulation.