# Nhut Nguyen # 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`. 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`. 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.