Validate Stack Sequences

Explanation & Solution

Description

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

Constraints

1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
All the elements of pushed are unique
popped.length == pushed.length
popped is a permutation of pushed

Approach

Stacks pattern

1. Simulate the Stack

Use a stack to simulate push and pop operations
Use a pointer j to track the current position in the popped array

2. Push and Greedily Pop

For each element in pushed:
Push it onto the stack
Then, while the stack's top matches popped[j]:
Pop it and advance j
This greedily pops whenever possible

3. Validate

After processing all pushes, if the stack is empty, all pops were valid → return true
If the stack is non-empty, the pop sequence was impossible → return false

Key Insight

The greedy approach works because each element is pushed exactly once
If we can pop an element that matches the next expected pop, we should — delaying never helps
Time: O(n), Space: O(n)

Solution Code

Removing Stars From a String

Remove K Digits