## Algorithm

Problem Name: 946. Validate Stack Sequences

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

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {
stacks1, s2;
int m = pushed.size(), n = popped.size();
for (int i = n - 1; i >= 0; --i) {
s2.push(popped[i]);
}

for (int i = 0; i < m; ++i) {
s1.push(pushed[i]);
while (!s1.empty() && !s2.empty() && s1.top() == s2.top()) {
s1.pop();
s2.pop();
}
}
return s2.empty();
}
};
``````
Copy The Code &

Input

cmd
pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

Output

cmd
true

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack stack = new Stack<>();
int pushIdx = 0;
int popIdx = 0;
while (pushIdx < pushed.length) {
while (!stack.isEmpty() && popped[popIdx] == stack.peek()) {
stack.pop();
popIdx++;
}
stack.push(pushed[pushIdx++]);
}
while (popIdx < popped.length) {
if (stack.isEmpty() || stack.peek() != popped[popIdx]) {
return false;
}
stack.pop();
popIdx++;
}
return true;
}
}
``````
Copy The Code &

Input

cmd
pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

Output

cmd
true

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const validateStackSequences = function(pushed, popped) {
const arr = []
for (let i = 0, len = pushed.length; i < len; i++) {
if (!helper(arr, pushed, popped)) return false
}
return true
}

function helper(arr, pu, po) {
let target = po

while (arr.length || pu.length) {
let curP = pu
if (curP === target) {
po.shift()
pu.shift()
return true
} else if (arr.length && arr[arr.length - 1] === target) {
arr.pop()
po.shift()
return true
} else {
if (curP == null) {
return false
} else {
arr.push(curP)
pu.shift()
}
}
}
return false
}
``````
Copy The Code &

Input

cmd
pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

Output

cmd
false

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def validateStackSequences(self, pushed, popped):
"""
:type pushed: List[int]
:type popped: List[int]
:rtype: bool
"""
arr, i = [], 0
for num in pushed:
arr.append(num)
while arr and arr[-1] == popped[i]:
i += 1
arr.pop()
return arr == popped[i:][::-1]
``````
Copy The Code &

Input

cmd
pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

Output

cmd
false

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0946_ValidateStackSequences
{
public bool ValidateStackSequences(int[] pushed, int[] popped)
{
var popIndex = 0;
var stack = new Stack();
foreach (var num in pushed)
{
stack.Push(num);
while (stack.Count > 0 && stack.Peek() == popped[popIndex])
{
stack.Pop();
popIndex++;
}
}

return popIndex == popped.Length;
}
}
}
``````
Copy The Code &

Input

cmd
pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

Output

cmd
true