Leetcode 946 - Validate Stack Sequence

Link to problem

Problem

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

Solution

We could simulate push and pop operation from the input and check if the simulated stack matches the pop sequence. i.e. if the simulated stack is empty by the end of the simulation.

Implementation

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> temp;
        int i = 0;

        for (auto n: pushed) {
            temp.push(n);
            while (!temp.empty() && temp.top() == popped[i]) {
                temp.pop();
                i++;
            }
        }

        return temp.empty();
    }
};