Interview Kickstart has enabled over 3500 engineers to uplevel.
The stack data structure is a big part of coding interviews at tech companies. This article will discuss one crucial previously asked FAANG problem on stacks.
Given: A stack of integers.
Task: Reverse the stack using recursion.
Constraints: We are not allowed to use any loop constructs like for, while, or do-while.
Here the initial stack was [1,2,3,4,5] and after reversing, it becomes [5,4,3,2,1].
The problem name itself declares the solution should be recursive.
The stack data structure has two methods: push and pop on the top of the stack. If we have to reverse the stack, we have to pop all elements from the original stack and push them in reverse order in some other stack. In this way, we get the new reversed stack.
However, it’s possible to do it without using extra stack objects, using recursion. A recursive function behaves like a stack. In this method, we will create the recursive function, pop all items from our stack, and store those popped items in the function call stack.
After popping all the items, the stack will become empty. Then, we will start pushing the new item, which the call stack of recursion contains. Finally, we will push them to the bottom of our empty stack.
In short, what we do is:
Visualization using an example:
using namespace std;
// Recursive function
// which inserts an element
// at the bottom of a stack.
void insert(int tp, stack<int> &st)
Here, the Function Call Stack holds all items until our stack is not empty.
When the stack becomes empty, we insert items in the stack; now, we will insert the items in the reverse order.
int a = st.top();
// Function that
// reverses the input stack
void recursiveReverse(stack<int> &st)
// Here we hold all items in Function
// Call Stack until stack is not empty.
int tp = st.top();
// Here, we push all the items that are on hold
// in Function Call Stack
// one by one. Every item is
// inserted at the bottom of the input stack.
// Creating stack objects.
// Pushing elements in the stack.
// Initial order of stack elements according to items placed.
cout << "Stack Initial: "
<< "5 4 3 2 1\n";
// Calling a recursive function to reverse the stack.
cout << "Stack Final: ";
// Popping elements one by one from stack and printing it.
int tp = st.top();
cout << tp << " ";
Stack Initial: 5 4 3 2 1
Stack Final: 1 2 3 4 5
Let us now discuss the time and space complexity of reversing a stack using recursion.
For each element on top of the stack, we’re popping the whole stack out, and then we’re placing that top element at the bottom, which uses O(n) operations. Moreover, we need to do these O(n) operations for every element in the input stack. Hence, there will be n2 operations that give the time complexity of O(n2).
We are using a recursion call stack to store the items in the input stack temporarily. In the worst case, there will be n items stored in the recursive call stack, making the space complexity O(n).
Visit the Interview Questions page for more sample interview questions asked at FAANG and other tier-1 tech companies.
Question 1: How to prove the time complexity of reversing a stack using recursion and recurrence relations?
Say there are n elements in the stack, according to our algorithm we are calling recursion and popping elements in it. in each recursive call we are popping one element. So, the recurrence relation will be:
T(n) = T(n-1) + n after popping one item
= T(n-2) + (n-1) + n after popping two items
= T(n-3) + (n-2) + (n-1) + n after popping three items
And so on, until we pop all the items in the stack.
The final relationship will be:
T(n) = T(n-(n-1)) + T(n-(n-2)) + … + (n-2) + (n-1) + n
= T(1) + T(2) + … + (n-2) + (n-1) + n
= 1 + 2 + … + (n-2) + (n-1) + n
= n × (n+1)/2
It gives the quadratic result; hence the complexity of reversing the stack using recursion will be O(n2).
Question 2: How are we inserting the top element at the bottom of the stack?
Let’s call the given stack an input stack. Now, we pass our input stack in the recursive function. According to the algorithm, in the recursive function, we pop the elements from the input stack and store them in the recursive call stack until the input stack becomes empty. After the input stack becomes empty, we push the top element, which the recursive stack in the input stack contains. Then, while returning down the recursion tree, we push all the elements stored in the recursive call stack one by one into the input stack.
Whether you’re a Coding Engineer gunning for Software Developer or Software Engineer roles, or you’re targeting management positions at top companies, IK offers courses specifically designed for your needs to help you with your technical interview preparation!
If you’re looking for guidance and help with getting started, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of Software Engineers to crack the most challenging coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
Article contributed by Omkar Deshkmukh