Problem statement

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.

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.

Constraints

• 1 <= pushed.length <= 1000.
• 0 <= pushed[i] <= 1000.
• All the elements of pushed are unique.
• popped.length == pushed.length.
• popped is a permutation of pushed.

Solution 1: Popping by erasure

Step 1. Go through pushed until the popping can be performed.

Step 2. Perform the popping by erasure as much as possible.

Step 3. Continue Step 1 and Step 2 until they cannot be performed anymore.

Example 1

With pushed = [1,2,3,4,5] and popped = [4,5,3,2,1]:

• Go through pushed starting from pushed.top = 1 until pushed.top = 4, when the popping can be performed because 4 == popped[0]. Only one popping can be performed. Erase (pop) that value, pushed becomes [1,2,3].
• Continue going through pushed, pushed.top = 5, and the popping can be performed since 5 == popped[1]. Now the popping can be performed fully all values of pushed and popped.
• End.

Code

#include <vector>
#include <iostream>
using namespace std;
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    int i = 0;
    int j = 0;
    while (i < pushed.size()) {
        // perform the popping by erasure as much as possible
        while (i >= 0 && pushed[i] == popped[j]) {
            pushed.erase(pushed.begin() + i);
            i--;
            j++;
        } 
        i++;
    }
    return pushed.empty();
}
int main() {
    vector<int> pushed{1,2,3,4,5};
    vector<int> popped{4,5,3,2,1};
    cout << validateStackSequences(pushed, popped) << endl;
    pushed = {1,2,3,4,5};
    popped = {4,3,5,1,2};
    cout << validateStackSequences(pushed, popped) << endl;
    pushed = {2,0,3,1};
    popped = {3,1,0,2};
    cout << validateStackSequences(pushed, popped) << endl;
}

Output:
1
0
1

Complexity

• Runtime: O(NlogN), where N = pushed.length. Though the complexity of vector::erase() is linear, the pushed.size() is reduced whenever the popping happened.
• Extra space: O(1).

Solution 2: Moving the top

Popping by erasure reduced the length of pushed. But using vector::erase() like that might cost some runtime.

Remember that popping and pushing are performed on the top of pushed. If a popping happened, a pushing right after that is simply a value reassignment on the top element.

Code

#include <vector>
#include <iostream>
using namespace std;
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    int i = 0; // index of pushed's top 
    int j = 0;
    for (int a : pushed) {
        pushed[i++] = a; // (re)assign a to the top element
        // perform the pop as much as possible
        while (i > 0 && pushed[i - 1] == popped[j]) { 
            i--;
            j++;
        } 
    }
    return i == 0;
}
int main() {
    vector<int> pushed{1,2,3,4,5};
    vector<int> popped{4,5,3,2,1};
    cout << validateStackSequences(pushed, popped) << endl;
    pushed = {1,2,3,4,5};
    popped = {4,3,5,1,2};
    cout << validateStackSequences(pushed, popped) << endl;
    pushed = {2,0,3,1};
    popped = {3,1,0,2};
    cout << validateStackSequences(pushed, popped) << endl;
}

Output:
1
0
1

Complexity

• Runtime: O(N), where N = pushed.length.
• Extra space: O(1).

Implementation note

• In the statement for (int a : pushed), all values a of the original pushed were stored in a copy of pushed. So you did not lose any of them.