946. Validate Stack Sequences
Problem Description
In this problem, we are given two integer arrays named pushed
and popped
respectively. Each array contains distinct values. The aim is to determine whether the sequence of integers in the popped
array could be the result of a certain sequence of push and pop operations on an initially empty stack by only using the integers given in the pushed
array, or not. To clarify, we want to know if we can push the numbers from the pushed
array onto the stack in the order they are given, and then pop them off to match the order they appear in the popped
array. We are to return true
if this is possible, or false
otherwise.
Intuition
The intuition behind the solution is to simulate the push and pop operations of a stack using the given pushed
and popped
arrays.
- We traverse the
pushed
array and push each element onto the stack. - After each push, we check if the stack's top element is equal to the current element at index
j
of thepopped
array. - If it is, we pop that element from the stack and increase the
j
index to move to the next element in thepopped
array. - We continue this process until either the stack is empty or the stack's top element is not equal to the
popped[j]
. - The stack simulates the push and pop operations, and the index
j
keeps track of the number of elements correctly popped from the stack. - If, after all push operations, the
j
index equals the length of thepushed
array, it means all elements were popped in thepopped
order, so we returntrue
. - If
j
is not equal to the length ofpushed
after the simulation, it means thepopped
sequence is not possible with the given push and pop operations, thus we returnfalse
.
The key insight is to recognize that the stack allows us to reorder elements as they are pushed and popped, but the popped
array creates a constraint on the order in which elements must be popped. The solution algorithm effectively tries to match these constraints by simulating the stack operations.
Learn more about Stack patterns.
Solution Approach
The solution uses a simple stack data structure and a loop to simulate the stack operations. Below is a step-by-step explanation of the solution:
-
Initialize an empty list
stk
that will act as our stack, and a variablej
to keep track of the current index in thepopped
array.j, stk = 0, []
-
Begin a loop to iterate over each value
v
in thepushed
array.for v in pushed:
-
Inside the loop, push the current element
v
onto the stack (stk
).stk.append(v)
-
After the push operation, enter a
while
loop that will run as long as the stack is not empty and the top element of the stack is equal to the element at the current indexj
of thepopped
array. This checks whether we can pop the top element to match the next element to be popped according to thepopped
sequence.while stk and stk[-1] == popped[j]:
-
If the top element on the stack is the same as
popped[j]
, pop it from the stack and incrementj
to check against the next element in thepopped
array. This simulates the pop operation and progresses the index as matching elements are found and popped.stk.pop() j += 1
-
After the loop has iterated through all elements in
pushed
, check if the indexj
is now the same as the length of thepushed
array. If it is, it means allpushed
elements have been successfully matched with thepopped
elements in the right order, so the function returnstrue
.return j == len(pushed)
-
If
j
is not equal tolen(pushed)
, it means not all elements could be matched, so the sequence of operations is not possible, and the function returnsfalse
.
In this solution, the stack data structure is essential since it allows elements to be accessed and removed in a last-in, first-out manner, which is exactly what we need to simulate the push and pop operations. The while
loop within the for
loop ensures that as soon as an element is pushed onto the stack, it is checked to see if it can be immediately popped off to follow the popped
sequence. This continues the checking and popping of elements without pausing the push operations, effectively interleaving the necessary operations to achieve the end goal.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Consider the following pushed
and popped
arrays:
pushed = [1, 2, 3, 4, 5] popped = [4, 5, 3, 2, 1]
Follow the steps outlined in the solution approach:
-
Initialize an empty stack
stk
andj
index to0
. -
Traverse the
pushed
array:-
v = 1
: Push 1 intostk
.stk = [1]
. Sincestk[-1]
(1) is not equal topopped[0]
(4), we continue without popping. -
v = 2
: Push 2 intostk
.stk = [1, 2]
. Sincestk[-1]
(2) is not equal topopped[0]
(4), we continue without popping. -
v = 3
: Push 3 intostk
.stk = [1, 2, 3]
. Sincestk[-1]
(3) is not equal topopped[0]
(4), we continue without popping. -
v = 4
: Push 4 intostk
.stk = [1, 2, 3, 4]
. Sincestk[-1]
(4) is equal topopped[0]
(4), we pop fromstk
and incrementj
. After popping,stk = [1, 2, 3]
andj = 1
.
-
-
Continue iterating and check the top against
popped[j]
. The new values ofj
andpopped
we compare against are as follows:-
Now
stk[-1]
is 3 andpopped[j]
is 5. They are not the same, so we move to push the next element frompushed
. -
v = 5
: Push 5 intostk
.stk = [1, 2, 3, 5]
. Now,stk[-1]
is 5, which matchespopped[j]
(5), so we pop 5 fromstk
, and nowstk = [1, 2, 3]
and incrementj
to 2. -
Now
stk[-1]
is 3, which matchespopped[j]
(3), so we pop 3 fromstk
, and nowstk = [1, 2]
and incrementj
to 3. -
Continue this comparison and popping process:
- Pop 2 from
stk
because it matchespopped[j]
(2), and nowstk = [1]
and incrementj
to 4. - Pop 1 from
stk
because it matchespopped[j]
(1), and nowstk
is empty and incrementj
to 5.
- Pop 2 from
-
-
Since we've finished iterating through
pushed
, we check ifj
is now equal to the length ofpushed
(which is 5):- Indeed,
j
is 5, which is the length ofpushed
, suggesting that all elements were popped in thepopped
order.
- Indeed,
Hence, for the given pushed
and popped
arrays, the simulation shows that it is possible to match the push and pop sequence, and the function should return true
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
5 # Initialize index to track the position in the 'popped' sequence
6 pop_index = 0
7
8 # Initialize an empty list to simulate stack operations
9 stack = []
10
11 # Iterate through each value in the 'pushed' sequence
12 for value in pushed:
13 # Push the current value onto the stack
14 stack.append(value)
15
16 # Check if the top of the stack matches the current value in 'popped'
17 # If it does, pop from the stack and advance the index in 'popped'
18 while stack and stack[-1] == popped[pop_index]:
19 stack.pop()
20 pop_index += 1
21
22 # If the pop_index is equal to the length of 'pushed', all elements were popped
23 # in the correct order, hence we return True. Otherwise, return False.
24 return pop_index == len(pushed)
25
26# Example usage:
27# solution = Solution()
28# result = solution.validateStackSequences([1, 2, 3, 4, 5], [4, 5, 3, 2, 1]) # True
29# result = solution.validateStackSequences([1, 2, 3, 4, 5], [4, 3, 5, 1, 2]) # False
30
1class Solution {
2
3 // Method to validate stack sequences using provided pushed and popped array sequences
4 public boolean validateStackSequences(int[] pushed, int[] popped) {
5 // Use a Deque as a stack for simulating the push and pop operations
6 Deque<Integer> stack = new ArrayDeque<>();
7
8 // Index for keeping track of the position in the popped sequence
9 int popIndex = 0;
10
11 // Iterate over the pushed sequence to simulate the stack operations
12 for (int num : pushed) {
13 // Push the current number onto the stack
14 stack.push(num);
15
16 // Keep popping from the stack if the top of the stack matches the current
17 // number in the popped sequence
18 while (!stack.isEmpty() && stack.peek() == popped[popIndex]) {
19 stack.pop(); // Pop from stack
20 popIndex++; // Move to the next index in the popped sequence
21 }
22 }
23
24 // If all elements were successfully popped in the correct sequence, the popIndex
25 // should be equal to the length of the pushed sequence
26 return popIndex == pushed.length;
27 }
28}
29
1#include <vector>
2#include <stack>
3
4class Solution {
5public:
6 // This function checks whether a given stack push and pop sequence is valid
7 bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
8
9 // Initialize an empty stack
10 stack<int> stack;
11
12 // The index for the popped sequence
13 int popIndex = 0;
14
15 // Iterate over each value in the pushed sequence
16 for (int value : pushed) {
17 // Push the current value onto the stack
18 stack.push(value);
19
20 // While the stack is not empty and the top of the stack is equal to
21 // the next value in the popped sequence
22 while (!stack.empty() && stack.top() == popped[popIndex]) {
23 // Pop the top value off the stack
24 stack.pop();
25 // Increment the pop sequence index
26 popIndex++;
27 }
28 }
29
30 // If the popIndex equals the size of the pushed sequence,
31 // then all elements were popped in the correct order
32 // Hence, the sequences are valid and the method returns true.
33 // If elements remain in the stack or the popIndex does not reach the end,
34 // then the sequences are not valid and the method returns false.
35 return popIndex == pushed.size();
36 }
37};
38
1function validateStackSequences(pushed: number[], popped: number[]): boolean {
2 // Initialize an empty array to simulate stack operations
3 const stack: number[] = [];
4 // Index to keep track of the position in the 'popped' sequence
5 let popIndex = 0;
6
7 // Iterate through each value in the 'pushed' sequence
8 for (const value of pushed) {
9 // Push the current value onto the stack
10 stack.push(value);
11 // Continue popping from the stack if the top element equals
12 // the next element in the 'popped' sequence
13 while (stack.length && stack[stack.length - 1] === popped[popIndex]) {
14 stack.pop(); // Remove the top element from the stack
15 popIndex++; // Move to the next index in the 'popped' sequence
16 }
17 }
18
19 // If all elements were successfully popped in the 'popped' sequence order,
20 // then the popIndex should match the length of the 'pushed' array
21 return popIndex === pushed.length;
22}
23
Time and Space Complexity
Time Complexity: The time complexity of the code is O(n)
, where n
is the length of the pushed
and popped
lists. The for loop runs for each element in pushed
, and while each element is pushed onto the stack once, the while loop may not necessarily run for every push operation as it depends on the match with the popped
sequence. However, each element will be popped at most once. Therefore, each element from pushed
is involved in constant-time push and pop operations on the stack, making the time complexity linear.
Space Complexity: The space complexity of the code is O(n)
. In the worst case, all the elements from the pushed
list could be stacked up in the stk
array (which happens when the popped
sequence corresponds to reversing the pushed
sequence), which would take up a space proportional to the number of elements in pushed
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!