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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
Google Coding Interview Question - Validate Stack Sequences (LeetCode) • AlgosWithMichael • 10,131 views views
Watch 9 more video solutions →Practice Validate Stack Sequences with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor