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.

---

Leetcode Problem #946 (Medium): Validate Stack Sequences

---

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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