946. Validate Stack Sequences - Explanation

Description

Start with an empty stack. Push all values in pushed in the given order, and pop all values in the order specified by popped. Pushes and pops may be interleaved. Return true if such an operation sequence exists, or false otherwise. All pushed values are distinct, and popped is a permutation of them. A pop removes the most recently pushed value that remains on the stack.

Example 1:

Input: pushed = [1,2,3]
popped = [2,1,3]

Output: true

Explanation: Push 1 and 2, pop 2 and 1, then push and pop 3. The pop order is exactly [2,1,3].

Example 2:

Input: pushed = [1,2,3]
popped = [3,1,2]

Output: false

Explanation: To pop 3 first, all three values must be pushed. Then 2 is on top of 1, so 1 cannot be popped next.

Example 3:

Input: pushed = [0]
popped = [0]

Output: true

Explanation: Push 0 and then pop it. This produces the requested single-value pop sequence.

Constraints:

1 <= pushed.length <= 1000
pushed.length == popped.length
0 <= pushed[i] <= 1000
All values in pushed are distinct.
popped is a permutation of pushed.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Stack Data Structure - Understanding push and pop operations and LIFO (Last-In-First-Out) behavior
Simulation - Mimicking a process step-by-step to verify if a sequence of operations is valid
Two Pointers - Using indices to track positions in multiple arrays simultaneously

1. Stack

Intuition

We can simulate the actual push and pop operations on a stack to verify if the sequences are valid. The key insight is that whenever we push an element, we should immediately try to pop as many elements as possible that match the expected pop sequence. If the simulation completes with an empty stack, the sequences are valid.

Algorithm

Initialize an empty stack and a pointer i to track position in the popped array.
Iterate through each element in the pushed array and push it onto the stack.
After each push, check if the stack top matches the current element in popped (at index i).
While there is a match, pop from the stack and increment the pointer i.
Continue until no more matches are found or the stack is empty.
After processing all elements, return true if the stack is empty, indicating all elements were successfully popped in the correct order.

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        i = 0
        stack = []
        for n in pushed:
            stack.append(n)
            while i < len(popped) and stack and popped[i] == stack[-1]:
                stack.pop()
                i += 1
        return not stack

public class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for (int n : pushed) {
            stack.push(n);
            while (i < popped.length && !stack.isEmpty() && popped[i] == stack.peek()) {
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

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

class Solution {
    /**
     * @param {number[]} pushed
     * @param {number[]} popped
     * @return {boolean}
     */
    validateStackSequences(pushed, popped) {
        const stack = [];
        let i = 0;
        for (const n of pushed) {
            stack.push(n);
            while (
                i < popped.length &&
                stack.length > 0 &&
                popped[i] === stack[stack.length - 1]
            ) {
                stack.pop();
                i++;
            }
        }
        return stack.length === 0;
    }
}

public class Solution {
    public bool ValidateStackSequences(int[] pushed, int[] popped) {
        Stack<int> stack = new Stack<int>();
        int i = 0;
        foreach (int n in pushed) {
            stack.Push(n);
            while (i < popped.Length && stack.Count > 0 && popped[i] == stack.Peek()) {
                stack.Pop();
                i++;
            }
        }
        return stack.Count == 0;
    }
}

func validateStackSequences(pushed []int, popped []int) bool {
    stack := []int{}
    i := 0
    for _, n := range pushed {
        stack = append(stack, n)
        for i < len(popped) && len(stack) > 0 && popped[i] == stack[len(stack)-1] {
            stack = stack[:len(stack)-1]
            i++
        }
    }
    return len(stack) == 0
}

class Solution {
    fun validateStackSequences(pushed: IntArray, popped: IntArray): Boolean {
        val stack = ArrayDeque<Int>()
        var i = 0
        for (n in pushed) {
            stack.addLast(n)
            while (i < popped.size && stack.isNotEmpty() && popped[i] == stack.last()) {
                stack.removeLast()
                i++
            }
        }
        return stack.isEmpty()
    }
}

class Solution {
    func validateStackSequences(_ pushed: [Int], _ popped: [Int]) -> Bool {
        var stack = [Int]()
        var i = 0
        for n in pushed {
            stack.append(n)
            while i < popped.count && !stack.isEmpty && popped[i] == stack.last! {
                stack.removeLast()
                i += 1
            }
        }
        return stack.isEmpty
    }
}

impl Solution {
    pub fn validate_stack_sequences(pushed: Vec<i32>, popped: Vec<i32>) -> bool {
        let mut stack = Vec::new();
        let mut i = 0;
        for &n in &pushed {
            stack.push(n);
            while i < popped.len() && !stack.is_empty() && popped[i] == *stack.last().unwrap() {
                stack.pop();
                i += 1;
            }
        }
        stack.is_empty()
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Two Pointers

Intuition

Instead of using a separate stack, we can reuse the pushed array itself as the stack. The left portion of the array acts as our stack, eliminating the need for extra space. This works because as we process elements, we overwrite positions that are no longer needed.

Algorithm

Use two pointers: l represents the top of our simulated stack within pushed, and r tracks position in popped.
Iterate through each element in pushed and write it to position l, then increment l.
After each write, check if the element at position l-1 matches popped[r].
While there is a match and l > 0, increment r and decrement l to simulate popping.
Continue processing all elements in pushed.
Return true if l equals 0, meaning all elements were successfully matched and popped.

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        l = r = 0
        for num in pushed:
            pushed[l] = num
            l += 1
            while l > 0 and pushed[l - 1] == popped[r]:
                r += 1
                l -= 1
        return l == 0

public class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int l = 0, r = 0;
        for (int num : pushed) {
            pushed[l++] = num;
            while (l > 0 && pushed[l - 1] == popped[r]) {
                r++;
                l--;
            }
        }
        return l == 0;
    }
}

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int l = 0, r = 0;
        for (int& num : pushed) {
            pushed[l++] = num;
            while (l > 0 && pushed[l - 1] == popped[r]) {
                r++;
                l--;
            }
        }
        return l == 0;
    }
};

class Solution {
    /**
     * @param {number[]} pushed
     * @param {number[]} popped
     * @return {boolean}
     */
    validateStackSequences(pushed, popped) {
        let l = 0,
            r = 0;
        for (const num of pushed) {
            pushed[l++] = num;
            while (l > 0 && pushed[l - 1] === popped[r]) {
                r++;
                l--;
            }
        }
        return l === 0;
    }
}

public class Solution {
    public bool ValidateStackSequences(int[] pushed, int[] popped) {
        int l = 0, r = 0;
        foreach (int num in pushed) {
            pushed[l++] = num;
            while (l > 0 && pushed[l - 1] == popped[r]) {
                r++;
                l--;
            }
        }
        return l == 0;
    }
}

func validateStackSequences(pushed []int, popped []int) bool {
    l, r := 0, 0
    for _, num := range pushed {
        pushed[l] = num
        l++
        for l > 0 && pushed[l-1] == popped[r] {
            r++
            l--
        }
    }
    return l == 0
}

class Solution {
    fun validateStackSequences(pushed: IntArray, popped: IntArray): Boolean {
        var l = 0
        var r = 0
        for (num in pushed) {
            pushed[l++] = num
            while (l > 0 && pushed[l - 1] == popped[r]) {
                r++
                l--
            }
        }
        return l == 0
    }
}

class Solution {
    func validateStackSequences(_ pushed: [Int], _ popped: [Int]) -> Bool {
        var pushed = pushed
        var l = 0
        var r = 0
        for num in pushed {
            pushed[l] = num
            l += 1
            while l > 0 && pushed[l - 1] == popped[r] {
                r += 1
                l -= 1
            }
        }
        return l == 0
    }
}

impl Solution {
    pub fn validate_stack_sequences(pushed: Vec<i32>, popped: Vec<i32>) -> bool {
        let mut pushed = pushed;
        let mut l = 0usize;
        let mut r = 0usize;
        let n = pushed.len();
        for idx in 0..n {
            pushed[l] = pushed[idx];
            l += 1;
            while l > 0 && pushed[l - 1] == popped[r] {
                r += 1;
                l -= 1;
            }
        }
        l == 0
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Popping Without Checking Stack Emptiness

When simulating stack operations, always verify the stack is non-empty before attempting to pop or access the top element. Failing to check this condition can lead to runtime errors or incorrect comparisons with an empty stack.

Not Popping Greedily After Each Push

The key insight is that after each push, you should immediately pop as many elements as possible that match the expected pop sequence. Delaying pops or only checking once at the end will lead to incorrect results because the order of operations matters in stack simulations.

Forgetting to Verify Complete Stack Emptiness

After processing all pushed elements, the stack must be completely empty for the sequences to be valid. If elements remain in the stack, it means not all pops could be matched, indicating an invalid sequence. Always check that the final stack size is zero.