# Validate Stack Sequences
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/validate-stack-sequences)
Canonical: https://scaleengineer.com/dsa/problems/validate-stack-sequences
**Data structures:** Array, Stack
**Companies:** [Apollo.io](https://scaleengineer.com/companies/apollo.io)
---
## Problem
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.

**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`.

# Approaches
## Simulation using a Stack
This approach simulates the entire push and pop process using an explicit stack data structure. We iterate through the `pushed` array, pushing each element onto our stack. After each push, we check if the top of the stack matches the next expected element in the `popped` array. If it does, we pop from the stack and advance our pointer in the `popped` array. We repeat this check until the stack is empty or the top doesn't match. Finally, if the entire `popped` sequence was valid, our stack should be empty at the end.
**Time:** O(N), where N is the length of the `pushed` and `popped` arrays. Each element is pushed and popped at most once. · **Space:** O(N), as in the worst-case scenario (e.g., `pushed = [1,2,3]`, `popped = [3,2,1]`), the stack can hold all N elements.
**Pros:** Conceptually simple and easy to implement.; Does not modify the input arrays.
**Cons:** Requires extra space proportional to the input size.
### Explanation
We use a `java.util.Stack` to mimic the operations. We also use a pointer, `j`, to keep track of our current position in the `popped` array. The logic directly follows the process of pushing elements from the `pushed` array and popping them whenever they match the sequence in the `popped` array. If at the end of this process the stack is empty, it means every pushed element was correctly popped, validating the sequence.

```java
import java.util.Stack;

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int j = 0; // pointer for popped array
        for (int x : pushed) {
            stack.push(x);
            while (!stack.isEmpty() && j < popped.length && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}
```
### Algorithm
*   Initialize an empty stack `st`.
*   Initialize an index `j = 0` for the `popped` array.
*   Iterate through each element `x` in the `pushed` array:
    *   Push `x` onto the stack `st`.
    *   While the stack `st` is not empty and its top element `st.peek()` is equal to `popped[j]`:
        *   Pop from the stack `st`.
        *   Increment `j`.
*   After the loop, if the stack `st` is empty, it means we have successfully simulated the sequence. Return `true`, otherwise return `false`.

## Space-Optimized Simulation (In-place)
This approach improves upon the first one by eliminating the need for an explicit stack. Instead, it cleverly reuses the `pushed` array as a stack. A pointer is used to manage the 'top' of this implicit stack. The logic remains the same: we iterate through the `pushed` elements, 'pushing' them into the front of the array, and then 'popping' them if they match the `popped` sequence.
**Time:** O(N), where N is the length of the arrays. The logic is identical to the first approach; we perform a single pass through the `pushed` array, and the inner while loop's total operations are bounded by N. · **Space:** O(1). We are modifying the input array in-place and do not use any auxiliary data structures whose size depends on the input N. This is constant extra space.
**Pros:** Highly space-efficient, using O(1) extra space.; Maintains the same optimal O(N) time complexity.
**Cons:** Modifies the input `pushed` array, which might be undesirable in some contexts.; The logic can be slightly less intuitive than using an explicit stack object.
### Explanation
Instead of a separate `Stack` object, we use the `pushed` array itself to function as a stack. We maintain a pointer, say `i`, which indicates the size of our stack (or the index of the next empty slot). The elements `pushed[0...i-1]` represent the elements currently in the stack. The core idea is that we iterate through the `pushed` values, placing them into the `pushed` array starting from index 0. The variable `i` acts as the stack pointer. When a value from `popped` matches the top of our implicit stack (`pushed[i-1]`), we simply decrement `i`, effectively popping the element. The sequence is valid if the implicit stack is empty (`i == 0`) at the end.

```java
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int i = 0; // pointer for the top of the stack in 'pushed'
        int j = 0; // pointer for 'popped' array
        for (int x : pushed) {
            pushed[i] = x; // push the element
            i++;
            while (i > 0 && j < popped.length && pushed[i - 1] == popped[j]) {
                i--; // pop the element
                j++;
            }
        }
        return i == 0; // check if the stack is empty
    }
}
```
### Algorithm
*   Initialize two pointers, `i = 0` (for the top of the implicit stack in `pushed`) and `j = 0` (for the `popped` array).
*   Iterate through each element `x` in the original `pushed` sequence:
    *   Place `x` at the current top of the stack: `pushed[i] = x`.
    *   Increment `i`.
    *   While `i > 0` (stack is not empty) and the top element `pushed[i-1]` is equal to `popped[j]`:
        *   Decrement `i` (effectively popping the element).
        *   Increment `j`.
*   After iterating through all elements, if the implicit stack is empty (i.e., `i == 0`), the sequence is valid. Return `true`, otherwise return `false`.

# Solutions
### CSharp

```csharp
public class Solution {
    public bool ValidateStackSequences(int[] pushed, int[] popped) {
        Stack < int > stk = new Stack < int > ();
        int j = 0;
        foreach(int x in pushed) {
            stk.Push(x);
            while (stk.Count != 0 && stk.Peek() == popped[j]) {
                stk.Pop();
                ++j;
            }
        }
        return stk.Count == 0;
    }
}
```

### Java

```java
class Solution {
public
  boolean validateStackSequences(int[] pushed, int[] popped) {
    Deque<Integer> stk = new ArrayDeque<>();
    int j = 0;
    for (int v : pushed) {
      stk.push(v);
      while (!stk.isEmpty() && stk.peek() == popped[j]) {
        stk.pop();
        ++j;
      }
    }
    return j == pushed.length;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} pushed * @param {number[]} popped * @return {boolean} */ var validateStackSequences =
  function (pushed, popped) {
    let stk = [];
    let j = 0;
    for (const v of pushed) {
      stk.push(v);
      while (stk.length && stk[stk.length - 1] == popped[j]) {
        stk.pop();
        ++j;
      }
    }
    return j == pushed.length;
  };

```

### CPP

```cpp
class Solution {
public:
  bool validateStackSequences(vector<int> &pushed, vector<int> &popped) {
    stack<int> stk;
    int j = 0;
    for (int v : pushed) {
      stk.push(v);
      while (!stk.empty() && stk.top() == popped[j]) {
        stk.pop();
        ++j;
      }
    }
    return j == pushed.size();
  }
};

```

### Python

```python
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool: j, stk = 0, [] for v in pushed: stk . append(v) while stk and stk[- 1] == popped[j]: stk . pop() j += 1 return j == len(pushed)

```