946. Validate Stack Sequences

📝 Problem Details

• Title: 946. Validate Stack Sequences
• Link: https://leetcode.com/problems/validate-stack-sequences/
• Difficulty: Medium
• Tags/Categories: Stack Simulation

input arrays pushed popped each array has distinct values return true if this could have been the result of a sequence of push and pop operations on an initially empty stack return false otherwise

💭What Were My Initial Thoughts?

we can essentially simulate the stack operations as if we were actually pushing and popping values from a stack
checking whether the given popped sequence could realistically result from the pushed sequence

💡 Explanation of Solution

- Initialize an empty stack and a pointer to the start of the popped array.
- Iterate through the pushed array, pushing each element onto the stack.
- After each push, check if the top of the stack matches the current element in popped.
    - If it does, pop from the stack and move the popped pointer forward.
- Repeat the above until we've processed all elements.
- If the stack is empty at the end, return true. Otherwise, return false.

⌛ Complexity Analysis

Time Complexity: O(n)
- Each element is pushed and popped at most once.

Space Complexity: O(n)
- A stack is used to simulate the operations.

💻 Implementation of Solution

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> stk;
        int popIndex = 0;
 
        for(int i=0; i < pushed.size(); i++) {
            stk.push(pushed[i]);
            // keep popping while top of the stack matches current popped value
            while(!stk.empty() && stk.top() == popped[popIndex]) {
                stk.pop();
                popIndex++;
            }
        }
        // if all elements are popped in the right order, the stack should be empty
        return stk.empty();
    }
};