# LeetCode 946: Validate Stack Sequences

## Problem Restatement

We are given two integer arrays:

```python
pushed
popped
```

Both arrays contain the same distinct values.

`pushed` gives the order in which values are pushed onto an initially empty stack.

`popped` gives a possible order in which values are popped from the stack.

Return `True` if `popped` could be produced by valid stack operations. Otherwise, return `False`.

The official statement asks whether `popped` could result from a sequence of push and pop operations on an initially empty stack, using the values from `pushed` in order.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Arrays `pushed` and `popped` |
| Output | `True` if the pop order is valid, otherwise `False` |
| Stack rule | Last in, first out |
| Push order | Must follow `pushed` exactly |
| Values | Distinct, and `popped` is a permutation of `pushed` |

Function shape:

```python
class Solution:
    def validateStackSequences(self, pushed: list[int], popped: list[int]) -> bool:
        ...
```

## Examples

Example 1:

```python
pushed = [1, 2, 3, 4, 5]
popped = [4, 5, 3, 2, 1]
```

This is valid.

One possible operation sequence is:

```text
push 1
push 2
push 3
push 4
pop 4
push 5
pop 5
pop 3
pop 2
pop 1
```

So the answer is:

```python
True
```

Example 2:

```python
pushed = [1, 2, 3, 4, 5]
popped = [4, 3, 5, 1, 2]
```

We can pop `4`, then `3`, then `5`.

But after that, the stack has:

```text
1, 2
```

with `2` on top.

So `1` cannot be popped before `2`.

Answer:

```python
False
```

## First Thought

We can directly simulate the stack.

The push order is fixed.

The only choice is when to pop.

So after every push, we should pop as many values as possible while the stack top matches the next required value in `popped`.

If the simulation can consume all values in `popped`, the sequence is valid.

## Key Insight

A stack only allows popping the top value.

So at any point, if:

```python
stack[-1] == popped[j]
```

then we should pop it immediately.

There is no benefit to waiting, because future pushes would only place more values above it and make it harder to pop now.

This greedy simulation is enough.

## Algorithm

Initialize:

```python
stack = []
j = 0
```

For each value `x` in `pushed`:

1. Push `x` onto the stack.
2. While the stack is not empty and the top equals `popped[j]`:
   - pop the stack
   - move `j` forward

At the end, return whether all popped values were matched:

```python
j == len(popped)
```

## Walkthrough

Use:

```python
pushed = [1, 2, 3, 4, 5]
popped = [4, 5, 3, 2, 1]
```

| Operation | Stack | Next needed |
|---|---|---|
| push `1` | `[1]` | `4` |
| push `2` | `[1, 2]` | `4` |
| push `3` | `[1, 2, 3]` | `4` |
| push `4` | `[1, 2, 3, 4]` | `4` |
| pop `4` | `[1, 2, 3]` | `5` |
| push `5` | `[1, 2, 3, 5]` | `5` |
| pop `5` | `[1, 2, 3]` | `3` |
| pop `3` | `[1, 2]` | `2` |
| pop `2` | `[1]` | `1` |
| pop `1` | `[]` | done |

All values in `popped` were matched.

Return:

```python
True
```

## Correctness

The algorithm pushes values in exactly the order given by `pushed`, so it respects the required push order.

After each push, it pops while the stack top equals the next required value in `popped`. Each such pop is valid because the value is at the top of the stack.

If the next required popped value is not at the top, it cannot be popped at that moment. The only possible action is to push more values, which is exactly what the algorithm does.

Whenever the top value matches the next required popped value, popping immediately is safe. Delaying that pop would only allow more pushed values to be placed above it, but the same value must still be popped before the later values below it can be reached.

Therefore, the simulation never rejects a sequence that could be valid.

If the algorithm matches all values in `popped`, it has built a valid sequence of stack operations, so it returns `True`.

If it cannot match all values, then some required pop order conflicts with the stack top order. No valid sequence can produce `popped`, so it returns `False`.

## Complexity

Let:

```python
n = len(pushed)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each value is pushed once and popped at most once |
| Space | `O(n)` | The stack may hold up to `n` values |

## Implementation

```python
class Solution:
    def validateStackSequences(self, pushed: list[int], popped: list[int]) -> bool:
        stack = []
        j = 0

        for x in pushed:
            stack.append(x)

            while stack and stack[-1] == popped[j]:
                stack.pop()
                j += 1

        return j == len(popped)
```

## Code Explanation

`stack` simulates the real stack:

```python
stack = []
```

`j` points to the next value we need to pop:

```python
j = 0
```

For every value in the push order, we push it:

```python
stack.append(x)
```

Then we repeatedly pop while the top matches the required pop value:

```python
while stack and stack[-1] == popped[j]:
    stack.pop()
    j += 1
```

At the end, if `j` reached the length of `popped`, every required pop was matched:

```python
return j == len(popped)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.validateStackSequences(
        [1, 2, 3, 4, 5],
        [4, 5, 3, 2, 1],
    ) is True

    assert s.validateStackSequences(
        [1, 2, 3, 4, 5],
        [4, 3, 5, 1, 2],
    ) is False

    assert s.validateStackSequences(
        [1],
        [1],
    ) is True

    assert s.validateStackSequences(
        [1, 2, 3],
        [1, 2, 3],
    ) is True

    assert s.validateStackSequences(
        [1, 2, 3],
        [3, 2, 1],
    ) is True

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard valid case | Requires interleaved push and pop |
| Standard invalid case | Violates stack top order |
| Single value | Minimum case |
| Pop immediately after each push | Fully increasing pop order |
| Pop after all pushes | Fully reversed pop order |