Description
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
pushed are unique.
popped.length == pushed.lengthpopped is a permutation of pushed.
Solutions
Solution 1: Stack Simulation
We iterate through the pushed array. For the current element x being iterated, we push it into the stack stk. Then, we check if the top element of the stack is equal to the next element to be popped in the popped array. If they are equal, we pop the top element from the stack and increment the index i of the next element to be popped in the popped array. Finally, if all elements can be popped in the order specified by the popped array, return true; otherwise, return false.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the pushed array.
PythonJavaC++GoTypeScriptRustJavaScriptC#
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stk = []
i = 0
for x in pushed:
stk.append(x)
while stk and stk[-1] == popped[i]:
stk.pop()
i += 1
return i == len(popped)(code-box)
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Deque<Integer> stk = new ArrayDeque<>();
int i = 0;
for (int x : pushed) {
stk.push(x);
while (!stk.isEmpty() && stk.peek() == popped[i]) {
stk.pop();
++i;
}
}
return i == popped.length;
}
}(code-box)
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> stk;
int i = 0;
for (int x : pushed) {
stk.push(x);
while (stk.size() && stk.top() == popped[i]) {
stk.pop();
++i;
}
}
return i == popped.size();
}
};(code-box)
func validateStackSequences(pushed []int, popped []int) bool {
stk := []int{}
i := 0
for _, x := range pushed {
stk = append(stk, x)
for len(stk) > 0 && stk[len(stk)-1] == popped[i] {
stk = stk[:len(stk)-1]
i++
}
}
return i == len(popped)
}(code-box)
function validateStackSequences(pushed: number[], popped: number[]): boolean {
const stk: number[] = [];
let i = 0;
for (const x of pushed) {
stk.push(x);
while (stk.length && stk.at(-1)! === popped[i]) {
stk.pop();
i++;
}
}
return i === popped.length;
}(code-box)
impl Solution {
pub fn validate_stack_sequences(pushed: Vec<i32>, popped: Vec<i32>) -> bool {
let mut stk: Vec<i32> = Vec::new();
let mut i = 0;
for &x in &pushed {
stk.push(x);
while !stk.is_empty() && *stk.last().unwrap() == popped[i] {
stk.pop();
i += 1;
}
}
i == popped.len()
}
}(code-box)
/**
* @param {number[]} pushed
* @param {number[]} popped
* @return {boolean}
*/
var validateStackSequences = function (pushed, popped) {
const stk = [];
let i = 0;
for (const x of pushed) {
stk.push(x);
while (stk.length && stk.at(-1) === popped[i]) {
stk.pop();
i++;
}
}
return i === popped.length;
};(code-box)
public class Solution {
public bool ValidateStackSequences(int[] pushed, int[] popped) {
Stack<int> stk = new Stack<int>();
int i = 0;
foreach (int x in pushed) {
stk.Push(x);
while (stk.Count > 0 && stk.Peek() == popped[i]) {
stk.Pop();
i++;
}
}
return i == popped.Length;
}
}(code-box)
