Validate Stack Sequences

How it works

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.

Steps

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

Complexity

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

Things to watch for

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.

from typing import List

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

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