Validate Stack Sequences - Solution & Explanation
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 <= 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.
This C solution initializes a stack and iterates through the pushed array. For each element, it checks if the stack's top element matches the next element in the popped array. If so, it pops the stack. Finally, it returns true if all elements were correctly popped, indicated by an empty stack.
Complexity
Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(n), for the stack storage used during the process.
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.
This C implementation utilizes a two-pointer technique by reusing the pushed array to simulate stack operations through in-place modifications using indexes. It keeps track of elements using two index pointers.
Complexity
Time Complexity: O(n), where n is the length of the arrays.
Space Complexity: O(1), as no extra space is used aside from input arrays.
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.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Simulate Stack Operations with a Single Stack | Time Complexity: O(n), where n is the number of elements in the array. |
| Two Pointer Technique | Time Complexity: O(n), where n is the length of the arrays. |
| Stack Simulation | — |
Detailed 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. |
Video Solution
Validate Stack Sequences - Leetcode 946 - Python • NeetCodeIO • 11,789 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Validate Stack Sequences easy or hard?
Validate Stack Sequences Python/Java solution
How to solve Validate Stack Sequences in O(n)?
What is the best approach for Validate Stack Sequences?
Is Validate Stack Sequences asked at Google/Amazon/Meta?
What data structure is used in Validate Stack Sequences?
What is the time complexity of Validate Stack Sequences?
Ready to solve this problem?
Practice Validate Stack Sequences with our built-in code editor and test cases.
Practice on FleetCode