Solution: Validate Stack Sequences
Tags: algorithms, javascript, java, python
Published: 2021-02-26 09:30:42

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/validate-stack-sequences/discuss/1083542).*

---

#### [Leetcode Problem #946 (*Medium*): Validate Stack Sequences](https://leetcode.com/problems/validate-stack-sequences/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
Given two sequences `pushed` and `popped` with **distinct values**, return `true` if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

---

#### ***Examples:***

>
Example 1:||
|---:|---|
Input:|pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output:|true
Explanation:|We might do the following sequence:<br>push(1), push(2), push(3), push(4), pop() -> 4,<br>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:***
>
 - `0 <= pushed.length == popped.length <= 1000`
 - `0 <= pushed[i], popped[i] < 1000`
 - `pushed` is a permutation of `popped`.
 - `pushed` and `popped` have distinct values.

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

So we can fairly easily solve this problem by just reconstructing the stack. If we iterate through **pushed** and push the values to a stack, then whenever the stack's top matches the current index (**j**) of **popped**, we know (because the numbers of the array are distinct) that we can pop the value off our stack and increment the popped index to match.

That would solve the problem in **O(N) time** and **O(N) space**, but we can make it even more efficient by doing an **in-place stack** using a **2-pointer system** with **pushed**. That drops our answer to **O(N) time** and **O(1) space**.

Instead of pushing the values to a separate stack array, we can just use the second pointer (**s**) in **pushed** to be the stack index and use **pushed** from **[0,s]** to represent our stack. This way, instead of pushing to an external stack array, we just overwrite the value of **pushed** representing the new top index of our stack (**pushed[s]**) with the current **pushed** value (**pushed[i]**).

When we're done with **pushed** values, if our "stack" has been depleted to empty (**s == 0**), then we can **return true**, otherwise **false**.

---

#### ***Implementation:***

For all but Java, **~s**, using the **bitwise NOT operator** (**~**), can function as a more efficient way of writing **s != -1**.

All but Javascript will need to check for boundary conditions on writing the new stack top.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var validateStackSequences = function(pushed, popped) {
    let len = pushed.length, i = 0, j = 0, s = 0
    while (i < len)
        if (~s && popped[j] === pushed[s]) j++, s--
        else pushed[++s] = pushed[++i]
    return !s
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        lenP, i, j, s = len(pushed), 0, 0, 0
        while i < lenP:
            if ~s and popped[j] == pushed[s]:
                j += 1
                s -= 1
            else:
                s += 1
                i += 1
                if i < lenP: pushed[s] = pushed[i]
        return not s
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int len = pushed.length, i = 0, j = 0, s = 0;
        while (i < len)
            if (s >= 0 && popped[j] == pushed[s]) {
                j++;
                s--;
            } else {
                s++;
                i++;
                if (i < len) pushed[s] = pushed[i];
            }
        return s == 0;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int len = pushed.size(), i = 0, j = 0, s = 0;
        while (i < len)
            if (~s && popped[j] == pushed[s]) j++, s--;
            else {
                s++, i++;
                if (i < len) pushed[s] = pushed[i];
            }
        return !s;
    }
};
```