Validate Stack Sequences solution and explanation
Google
9 more videos on this problem
Validate Stack Sequences - Leetcode 946 - PythonNeetCodeIO · 6:23 · 11K views
Validate Stack Sequences | Leetcode - 946 | AMAZON | Explanation ➕ Live CodingcodestorywithMIK · 11:04 · 8K views
Validate Stack Sequences | Live Coding with Explanation | Leetcode - 946Algorithms Made Easy · 6:34 · 6K views
Validate Stack Sequences || Two Pointers || Stacks || Leetcode - 946 || C++/Java/PythonAryan Mittal · 19:12 · 1K views
Validate Stack Sequences | LeetCode 946 | Google | Constant SpaceNaresh Gupta · 9:00 · 1K views
LeetCode 946: Validate Stack SequencesEngineering Digest · 7:12 · 790 views
LeetCode 946. [Medium] Validate Stack SequencesFrancesco Manicardi · 5:57 · 524 views
Validate Stack Sequences | Leetcode 946Coding Decoded · 8:16 · 485 views
Validate Stack Sequences | Leetcode 946 | Stacks | Live coding session🔥🔥Coding Decoded · 1:06 · 436 views
946 Validate Stack Sequencescstutorials · 5:34 · 189 views
The problem
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.
Approach overview
Problem Overview: You get two integer arrays: pushed and popped. The first represents the order elements are pushed onto a stack. The second represents a possible pop order. The task is to verify whether the popped sequence could be produced by valid stack operations.
Approach 1: Simulate Stack Operations with a Single Stack (O(n) time, O(n) space)
This approach directly models how a real stack behaves. Iterate through the pushed array and push each value onto a stack. After every push, repeatedly check whether the stack’s top matches the next element in popped. If it matches, pop it and advance the pointer in popped. This greedy process works because whenever the top equals the required pop value, the pop must occur immediately for the sequence to remain valid.
The key insight: if the sequence is valid, every element must eventually appear at the stack top exactly when the pop sequence expects it. Using a stack keeps track of elements that have been pushed but not yet popped. Each value is pushed once and popped at most once, leading to O(n) time and O(n) extra space. This method heavily relies on stack semantics and is a classic application of stack simulation combined with sequential processing of arrays.
Approach 2: Two Pointer Technique (O(n) time, O(n) space)
The same idea can be expressed using two indices that track progress in pushed and popped. Use pointer i for iterating through pushed and pointer j for the current target in popped. As elements are pushed into a simulated stack, keep checking whether the top matches popped[j]. If it does, pop and increment j. Continue until all elements in pushed are processed.
The two-pointer view clarifies that the algorithm only moves forward through both arrays. Each element is processed once during push and at most once during pop. This produces the same O(n) time complexity while maintaining O(n) auxiliary space for the stack. The logic is often categorized under simulation because it reproduces the exact push/pop behavior defined by stack rules.
Recommended for interviews: The stack simulation approach is what interviewers typically expect. It mirrors the real data structure behavior and demonstrates that you understand stack constraints. Explaining the reasoning—push until you can match the next pop, then pop greedily—shows clear problem modeling. The two-pointer framing is essentially the same algorithm but helps communicate why the solution runs in linear time.
Approach 1: Simulate Stack Operations with a Single Stack
The key idea is to use a stack to simulate the push and pop operations. We iterate over each element in the pushed array, pushing them onto the stack. After each push, we check the top of the stack to see if it matches the next element in the popped array. If it does, we pop the stack. By the end of both arrays, if all operations are valid, the stack should be empty.
def validateStackSequences(pushed, popped):
stack = []
j = 0
for x in pushed:
stack.append(x)
while stack and stack[-1] == popped[j]:
stack.pop()
j += 1
return not stackimport java.util.Stack;
public class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int j = 0;
for (int x : pushed) {
stack.push(x);
while (!stack.isEmpty() && stack.peek() == popped[j]) {
stack.pop();
j++;
}
}
return stack.isEmpty();
}
}#include <vector>
#include <stack>
bool validateStackSequences(std::vector<int>& pushed, std::vector<int>& popped) {
std::stack<int> stack;
int j = 0;
for (int x : pushed) {
stack.push(x);
while (!stack.empty() && stack.top() == popped[j]) {
stack.pop();
j++;
}
}
return stack.empty();
}function validateStackSequences(pushed, popped) {
const stack = [];
let j = 0;
for (const x of pushed) {
stack.push(x);
while (stack.length && stack[stack.length - 1] === popped[j]) {
stack.pop();
j++;
}
}
return stack.length === 0;
}#include <stdbool.h>
bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) {
int stack[pushedSize];
int top = -1, j = 0;
for (int i = 0; i < pushedSize; i++) {
stack[++top] = pushed[i]; // Push operation
while (top >= 0 && stack[top] == popped[j]) { // Check if top of stack equals next popped value
top--;
j++;
}
}
return top == -1;
}using System.Collections.Generic;
public class Solution {
public bool ValidateStackSequences(int[] pushed, int[] popped) {
Stack<int> stack = new Stack<int>();
int j = 0;
foreach (int x in pushed) {
stack.Push(x);
while (stack.Count > 0 && stack.Peek() == popped[j]) {
stack.Pop();
j++;
}
}
return stack.Count == 0;
}
}This Python solution also simulates stack pushes and pops as described. Lists are used to simulate a stack here, enabling append and pop operations efficiently.
Time Complexity: O(n), where n is the length of the pushed/popped lists.
Space Complexity: O(n), due to space for the stack.
Approach 2: Two Pointer Technique
In this approach, you can use two pointers to bypass the use of an explicit stack. You iterate over the pushed array with one pointer while another pointer operates over the popped array. Match elements and mimic stack operations conceptually.
def validateStackSequences(pushed, popped):
i, j, k = 0, 0, 0
while i < len(pushed):
pushed[k] = pushed[i]
k += 1
i += 1
while k > 0 and pushed[k - 1] == popped[j]:
k -= 1
j += 1
return k == 0public class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
int i = 0, j = 0, k = 0;
while (i < pushed.length) {
pushed[k++] = pushed[i++]; // Use pushed array as storage
while (k > 0 && pushed[k - 1] == popped[j]) {
k--;
j++;
}
}
return k == 0;
}
}#include <vector>
bool validateStackSequences(std::vector<int>& pushed, std::vector<int>& popped) {
int i = 0, j = 0, k = 0;
while (i < pushed.size()) {
pushed[k++] = pushed[i++]; // Use pushed array as a stack
while (k > 0 && pushed[k - 1] == popped[j]) {
k--;
j++;
}
}
return k == 0;
}function validateStackSequences(pushed, popped) {
let i = 0, j = 0, k = 0;
while (i < pushed.length) {
pushed[k++] = pushed[i++]; // Override in pushed
while (k > 0 && pushed[k - 1] === popped[j]) {
k--;
j++;
}
}
return k === 0;
}#include <stdbool.h>
bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) {
int i = 0, j = 0, k = 0;
while (i < pushedSize) {
pushed[k++] = pushed[i++]; // Use pushed array as a stack
while (k > 0 && pushed[k - 1] == popped[j]) {
k--;
j++;
}
}
return k == 0;
}public class Solution {
public bool ValidateStackSequences(int[] pushed, int[] popped) {
int i = 0, j = 0, k = 0;
while (i < pushed.Length) {
pushed[k++] = pushed[i++]; // Reuse pushed array
while (k > 0 && pushed[k - 1] == popped[j]) {
k--;
j++;
}
}
return k == 0;
}
}In this Python code, the same two-pointer approach is leveraged by directly working on indexes of the pushed array similar to using a stack. It checks and manages elements consistency using these pointers.
Time Complexity: O(n), where n matches the arrays' length.
Space Complexity: O(1), achieved using in-place transformations.
Approach 3: 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.
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;
}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)
}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()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simulate Stack Operations with a Single Stack | Time Complexity: O(n), where n is the length of the pushed/popped lists. |
| Two Pointer Technique | Time Complexity: O(n), where n matches the arrays' length. |
| Stack Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Stack Operations with a Single Stack | O(n) | O(n) | General case. Most intuitive and mirrors real stack behavior. |
| Two Pointer Technique with Stack Simulation | O(n) | O(n) | When explaining algorithm flow using indices for pushed and popped arrays. |
Frequently asked questions
Is Validate Stack Sequences easy or hard?
Validate Stack Sequences is classified as a Medium difficulty problem on LeetCode. The logic is straightforward once you recognize it as a stack simulation problem, but identifying the greedy pop condition can take practice.
Validate Stack Sequences Python/Java solution
Python and Java implementations typically use a list or Stack/Deque structure to simulate push and pop operations. The algorithm pushes values from the pushed array and pops whenever the top matches the next value in popped, maintaining O(n) time complexity.
How to solve Validate Stack Sequences in O(n)?
Iterate through the pushed array while pushing elements onto a stack. After each push, check if the stack’s top equals the current value in popped. If it matches, pop from the stack and advance the popped pointer. Continue until all pushes are processed and verify the stack is empty.
What is the best approach for Validate Stack Sequences?
Stack simulation is the most effective approach. Push elements from the pushed array and pop whenever the stack top matches the next element in popped. Each element is pushed and popped at most once, resulting in O(n) time and O(n) space complexity.
Is Validate Stack Sequences asked at Google/Amazon/Meta?
Stack simulation problems like Validate Stack Sequences frequently appear in technical interviews at companies such as Amazon, Google, and Meta. They test understanding of stack behavior, sequence validation, and linear-time simulation techniques.
What data structure is used in Validate Stack Sequences?
A stack is the core data structure used in this problem. It tracks elements that have been pushed but not yet popped, allowing the algorithm to verify whether the required pop order is valid.
What is the time complexity of Validate Stack Sequences?
The optimal solution runs in O(n) time because every element is processed once during push and at most once during pop. The auxiliary stack stores at most n elements, giving O(n) space complexity.