Algorithm
Problem Name: 946. Validate Stack Sequences
Problem Link: https://leetcode.com/problems/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 <= 10000 <= pushed[i] <= 1000- All the elements of
pushedare unique. popped.length == pushed.lengthpoppedis a permutation ofpushed.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack < int>s1, 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();
}
};
Input
Output
#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;
}
}
Input
Output
#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[0]
while (arr.length || pu.length) {
let curP = pu[0]
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
}
Input
Output
#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]
Input
Output
#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 < int>();
foreach (var num in pushed)
{
stack.Push(num);
while (stack.Count > 0 && stack.Peek() == popped[popIndex])
{
stack.Pop();
popIndex++;
}
}
return popIndex == popped.Length;
}
}
}
Input
Output