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] <= 1000pushed are unique.popped.length == pushed.lengthpopped is a permutation of pushed.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.
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.
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.
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.
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.
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.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| 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 | — |
| 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. |
Validate Stack Sequences - Leetcode 946 - Python • NeetCodeIO • 11,476 views views
Watch 9 more video solutions →Practice Validate Stack Sequences with our built-in code editor and test cases.
Practice on FleetCode