Code Implementation

class Solution:
    def validateStackSequences(self, pushed, popped):
        stack = []
        j = 0
        for x in pushed:
            stack.append(x)
            while stack and j < len(popped) and stack[-1] == popped[j]:
                stack.pop()
                j += 1
        return j == len(popped)
      

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

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

var validateStackSequences = function(pushed, popped) {
    let stack = [];
    let j = 0;
    for (let x of pushed) {
        stack.push(x);
        while (stack.length > 0 && j < popped.length && stack[stack.length - 1] === popped[j]) {
            stack.pop();
            j++;
        }
    }
    return j === popped.length;
};
      

Problem Description

Given two integer arrays pushed and popped of the same length, you must determine if this popped sequence could have been the result of a sequence of stack operations (push and pop) performed on an initially empty stack, where the push operations are done in the order of pushed and each element is pushed exactly once. Each element must be popped exactly once and cannot be reused. There is only one valid stack sequence for each pushed array, and you cannot rearrange the push order.

• Each element in pushed and popped is unique.
• You can only push the next element from pushed or pop from the top of the stack.
• Return true if popped is a valid pop sequence for pushed; otherwise, return false.

Thought Process

At first, you might think about simulating every possible sequence of stack operations to see if popped can be generated from pushed. However, this brute-force approach is inefficient and unnecessary. Instead, it's better to simulate the stack process directly, pushing elements as in pushed and popping when the top of the stack matches the next element in popped.

The key insight is to use a stack to mimic the process: push elements from pushed one by one, and whenever the top of the stack matches the next element in popped, pop it. If we can pop all elements in popped this way, the sequence is valid.

Solution Approach

• Initialize an empty stack and a pointer j to track the position in popped.
• Iterate through each element x in pushed:
  • Push x onto the stack.
  • After each push, check if the stack is not empty and the top of the stack equals popped[j]:
    • If so, pop from the stack and increment j.
    • Repeat this check (in a loop) in case multiple pops are possible in a row.
• After processing all elements, if j equals the length of popped, return true; otherwise, return false.

This approach efficiently simulates the stack operations and checks validity in a single pass through the arrays.

Example Walkthrough

Consider pushed = [1,2,3,4,5] and popped = [4,5,3,2,1].

1. Push 1 (stack = [1]), top != 4.
2. Push 2 (stack = [1,2]), top != 4.
3. Push 3 (stack = [1,2,3]), top != 4.
4. Push 4 (stack = [1,2,3,4]), top == 4, pop (stack = [1,2,3], j = 1).
5. Top now 3 != 5, so push 5 (stack = [1,2,3,5]), top == 5, pop (stack = [1,2,3], j = 2).
6. Top == 3, pop (stack = [1,2], j = 3).
7. Top == 2, pop (stack = [1], j = 4).
8. Top == 1, pop (stack = [], j = 5).

All elements in popped are matched and the stack is empty, so the sequence is valid.

Time and Space Complexity

• Brute-force approach: Would involve generating all possible stack operation sequences, which is exponential in time and not feasible for large inputs.
• Optimized approach (above):
  • Time Complexity: O(N), where N is the length of the input arrays. Each element is pushed and popped at most once.
  • Space Complexity: O(N) for the stack, since in the worst case all elements could be on the stack at once.

Summary

This problem is elegantly solved by simulating stack operations with a single stack and two pointers. By pushing elements from pushed and popping whenever possible to match popped, we efficiently determine if the pop sequence is valid. The solution is both simple and efficient, requiring only linear time and space, and directly models the behavior of a real stack.