Sort A Stack Using Another Stack
Difficulty: Medium
Asked in: Amazon, Microsoft, VMWare
Understanding the Problem
Problem Description
You are given a stack of integers, write a program to sort it. You could use another stack if needed.
Problem Note
- The top of the stack must point to the smallest element.
- The stack must be sorted in increasing order from the top of the stack to its bottom.
Example 1
Input: Top -> [4,3,1,6,2,5]
Output: Top -> [1,2,3,4,5,6]
Example 2
Input: Top -> [1,2,3]
Output: Top -> [1,2,3]
Example 3
Input: Top -> [10,9,3,1]
Output: Top -> [1,3,9,10]
You can first try to solve this problem here.
Solutions
We will be discussing two different approaches:-
- Sorting using another stack
- Sorting using recursion
1. Sorting Using Another Stack
A stack performs push and pop operations. So, the push and pop operations are carried out between the input_stack and the auxilary_stack in such a way that the auxiliary stack contains the sorted input stack.
Consider this Example
— Consider the input stack is
[1, 2, 5, 3, 4]
Element taken out: 1
Input Stack: [2, 5, 3, 4]
Aux Stack: [1]
Element taken out: 4
Input Stack: [2, 5, 3]
Aux Stack: [1, 4]
Element taken out: 3
Input Stack: [2, 5, 4]
Aux Stack: [1]
Element taken out: 3
Input Stack: [2, 5, 4]
Aux Stack: [1, 3]
Element taken out: 4
Input Stack: [2, 5]
Aux Stack: [1, 3, 4]
Element taken out: 5
Input Stack: [2]
Aux Stack: [1, 3, 4, 5]
Element taken out: 2
Input Stack: [5]
Aux Stack: [1, 3, 4]
Element taken out: 2
Input Stack: [5, 4]
Aux Stack: [1, 3]
Element taken out: 2
Input Stack: [5, 4, 3]
Aux Stack: [1]
Element taken out: 2
Input Stack: [5, 4, 3]
Aux Stack: [1, 2]
Element taken out: 3
Input Stack: [5, 4]
Aux Stack: [1, 2, 3]
Element taken out: 4
Input Stack: [5]
Aux Stack: [1, 2, 3, 4]
Element taken out: 5
Input Stack: []
Aux Stack: [1, 2, 3, 4, 5]
Output - [1, 2, 3, 4, 5]
If you will go through this example, you will understand what is happening behind the hood.
Solution Steps
- Create a temporary stack say aux_stack .
- Repeat until the input_stack is not empty
- Pop an element from input_stack call it temp_value.
- While aux_stack is not empty and top of the aux_stack < temp_value , pop data from aux_stack and push it to the input_stack
- Push temp_value to the aux_stack
- return the aux_stack .
Pseudo Code
Stack sort_stack(Stack input_stack) {
Stack aux_stack
while(!input_stack.empty())
{
int temp_value = input_stack.top()
input_stack.pop()
while(!aux_stack.empty() and aux_stack.top() > temp) {
input_stack.push(aux_stack.top())
aux_stack.pop()
}
aux_stack.push(temp_value)
}
return aux_stack
}
Complexity Analysis
Time Complexity: O(n²)
Space Complexity: O(n)
Critical Ideas to Think
- Why did we pop from the aux_stack if the top is less than temp?
- What changes will you make in this pseudo-code to sort the stack in decreasing order?
- What would be the worst-case for this approach?
2. Sort stack using recursion
The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one in sorted order.
Consider this example:
First pop all the elements from the stack and store popped element in variable ‘temp’. After poping all the elements function’s stack frame will look like:
temp = 4 --> stack frame #1
temp = 3 --> stack frame #2
temp = 2 --> stack frame #3
temp = 5 --> stack frame #4
temp = 1 --> stack frame #5
Now stack is empty and ‘insert_in_sorted_order()’ function is called and it inserts 1 (from stack frame #5) at the bottom of the stack. Now stack looks like below:
1 <-- top of the stack
Now next element i.e. 5 (from stack frame #4) is picked. Since 5 > 1, 5 is inserted at the bottom of the stack. Now stack becomes:
1 <-- top of the stack
5
Next 2 (from stack frame #3) is picked. Since 2 > 1, 2 is inserted below 1. Now stack becomes:
1 <-- top of the stack
2
5
Next 3 (from stack frame #2) is picked. Since 3 > 1 and 3 > 2, it is inserted below 2. Now stack becomes:
1 <-- top of the stack
2
3
5
Now 4 (from stack frame #1) is picked, as 4 > 1 and 4 > 2 and 4 > 3, it is inserted below 3. Now stack becomes:
1 <-- top of the stack
2
3
4
5
Solution Steps
Create these two functions →
sort_stack(stack)
- If the stack is not empty,
- pop the element from the stack and store it in a temp variable
- call sort_and_insert(stack, temp)
sort_and_insert(stack, temp)
- If the stack is empty or temp < stack.top()
- then push temp to the top of the stack otherwise, pop data from the stack and store it in temp2.
- call sort_and_insert(stack, temp)
- and then push(stack, temp2)
Pseudo Code
// Utility Function
void sort_stack_and_insert(stack s, int data) {
if (isEmpty(s) or data < s.top()) {
push(s, data)
return
}
temp = s.pop()
sort_stack_and_insert(s, data)
push(s, temp)
}
// Driver function
stack sort_stack(stack s) {
if (!isEmpty(s))
{
int data = s.pop()
sort_stack(s)
sort_stack_and_insert(s, data)
}
return s
}
Complexity Analysis
Time Complexity: O(n²)
Space Complexity: O(n), due to n stack frames during recursion.
Critical Ideas to Think
- Do you think that if you will convert the first approach to recursive from iterative, then both of the approaches become the same?
- Do you understand how the stack is being sorted in the recursion tree?
Comparison of Different Approaches
Suggested Problems to Solve
- Min Stack problem
- Evaluate a given Expression
If you have any more approaches or you find an error/bug in the above solutions, please comment down below.
Happy Coding! Enjoy Algorithms!