Given two sequences pushed and popped with distinct values, return true if and only if this could have been the result of a sequence of push and pop operations on an initially empty stack.

Example 1:
Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Note:
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed is a permutation of popped.
pushed and popped have distinct values.

How to Validate a Stack Sequence using a Stack and Greedy Algorithm?

Let’s use a stack to simulate the push operations (in order) to the stack, and pop the elements if they are next to pop.

Let’s say if the top of the stack is 1, and the next element to pop is also 1, we have to pop it from the stack otherwise, any subsequent push will overwrite the top of the stack and the element we want to pop next will not be ever popped.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

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

When all the elements are pushed, we have to check if the number of popped elements is the same as the number of pushed elements to the stack.

The above C++ solution to validate the stack sequences run at O(N) time and O(N) space respectively.

–EOF (The Ultimate Computing & Technology Blog) —