Play this article

# 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.