## DEV Community is a community of 852,088 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Solution: Validate Stack Sequences

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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:
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:

• `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:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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:

``````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:

``````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:

``````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:

``````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;
}
};
``````