1/2/25, 12:15 PM Validate Stack Sequences
AfterAcademy
Admin AfterAcademy
5 Oct 2020
Validate Stack Sequences
Difficulty: Medium
Understanding The Problem
Problem Statement
Given two sequences pushed and popped with distinct values, write a
program to return true if and only if this could have been the result of a
https://afteracademy.com/blog/validate-stack-sequences/ 1/7
1/2/25, 12:15 PM Validate Stack Sequences
sequence of push and pop operations on an initially empty stack.
Problem Note
pushed is a permutation of popped.
pushed and popped have distinct values.
Example 1
Input: pushed = [5, 10, 15, 20, 25], popped = [20, 25, 15, 10, 5]
Output: 1
Explanation: We might do the following sequence:
push(5), push(10), push(15), push(20), pop() -> 20,
push(25), pop()-> 25, pop()-> 15, pop()-> 10, pop()-> 5
Example 2
Input: pushed = [5, 10, 15, 20, 25], popped = [20, 15, 25, 5, 10]
Output: 0
Explanation: 5 cannot be popped before 10.
Solution
To validate the pushed and popped operation on an empty stack, we can
follow a Greedy approach. A stack performs two operations push to the top
of the stack and pop from the top of the stack.
The sequence will be valid if we can perform push and pop operation such
that all the values stored in the pushed and popped array will be
exhausted without interfering with the sequence.
How can we use a stack to solve this problem?
The simpler way to proceed is to use an empty stack and start pushing the
elements of the pushed array sequentially in the stack and comparing
https://afteracademy.com/blog/validate-stack-sequences/ 2/7
1/2/25, 12:15 PM Validate Stack Sequences
every top element of the stack with the front element of the popped array.
If the top element of the stack is at the front of the popped array then we
can pop the element from the stack and increment the popped array
pointer by one, otherwise, we can push the front element of the pushed
array in the stack and increment the popped array pointer by one. If in this
process, all the elements of the popped array gets exhausted, then our
sequence is valid.
Try this problem here.
Solution Step
1. Create an empty stack and push the first element of pushed array
2. Place two pointers on the pushed and popped array.
3. Compare the top element of the stack with the front element of
popped array
If both of them are the same, then we have to pop the top element of
the stack and increment the popped array pointer by one
If both of them are not the same, then we have to push the front
element of pushed array into the stack and increment the pushed
array pointer by one
4. Repeat step 2 to 3, until the stack becomes empty.
Pseudo Code
bool validateStackSequences(int[] pushed, int[] popped) {
Stack stack
int j = 0
for (int i = 0 to i < pushed.size()) {
stack.push(pushed[i])
https://afteracademy.com/blog/validate-stack-sequences/ 3/7
1/2/25, 12:15 PM Validate Stack Sequences
while (stack is not empty and stack.top() is popped[j]) {
stack.pop()
j = j + 1
}
}
if(stack is empty)
return true
else
return false
}
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n) (How?)
Critical Ideas To Think
We have used while loop inside a for loop, then how come the time
complexity is O(n)? Answer: If we follow the logic of pseudocode, we
are visiting each element of pushed and popped array only once.
What will be the case when the stack will not be empty at the end?
Answer: When we have an invalid sequence, the stack will not be empty
at the end. Try the above example 2 on this pseudocode.
How this is a greedy approach? Read here to learn about greedy
algorithms.
What does the variable j represent in the pseudocode?
Can we solve this problem by using a queue, instead of a stack?
Will this approach work if the pushed array contains repeated
elements?
Suggested Problems To Solve
https://afteracademy.com/blog/validate-stack-sequences/ 4/7
1/2/25, 12:15 PM Validate Stack Sequences
Activity selection problem
Huffman coding
Water connection problem
Graph coloring
Please comment down below if you have a better insight in the above approach.
Happy Coding, Enjoy Algorithms!
Recommended for You
Reverse a Stack Using Largest Rectangle in a
Recursion Histogram-Interview Problem
Given a stack of integers st, write a program You are given an array of integers arr where
to reverse the stack using recursion. This each element represents the height of a bar
problem will clear the concept of recursion. in a histogram. Histogram is a graphical
display of data using bars of different
heights. The bars are placed in the exact
same sequence as given in the array. You
need to find the area of the largest rectangle
found in the given histogram.
Admin AfterAcademy Admin AfterAcademy
6 Oct 2020 16 Jun 2020
https://afteracademy.com/blog/validate-stack-sequences/ 5/7
1/2/25, 12:15 PM Validate Stack Sequences
Valid Anagram Min Stack Problem
Write a program to check whether the two This is an interview problem asked in
strings are an anagram of each other or not. companies like Amazon, Microsoft, Yahoo
Like, "s" is an anagram of "t" if the and Adobe. The problem is to design a
characters of "s" can be rearranged to form stack that will support push(), pop(), top()
"t". This simple problem will let you and getMin() operation in constant time. We
understand the concepts of string will be discussing two different ways to
manipulation. approach this problem.
Admin AfterAcademy Admin AfterAcademy
11 Jun 2020 1 May 2020
Implement Queue Using Stack- Find an Element In a Bitonic
Interview Problem Array
This is an interview problem asked in Given a bitonic sequence of n distinct
companies like Microsoft, Amazon, Adobe, elements, write a program to search a given
Flipkart, etc. Here, we need to implement element k in the bitonic sequence. Bitonic
Queue data structure using another data Sequence is a sequence of numbers that is
structure Stack. This problem is meant for first strictly increasing then after a point
testing the data structure knowledge. strictly decreasing.
Admin AfterAcademy Admin AfterAcademy
16 Mar 2020 23 Mar 2020
https://afteracademy.com/blog/validate-stack-sequences/ 6/7
1/2/25, 12:15 PM Validate Stack Sequences
Connect With Your Mentors
Janishar Ali Amit Shekhar
Founder | IIT-BHU | 10 Yrs Exp. Founder | IIT-BHU | 10 Yrs Exp.
Copyright 2022, MindOrks Nextgen Private Limited
https://afteracademy.com/blog/validate-stack-sequences/ 7/7
