Difficulty: Medium, Asked-in: Amazon, Microsoft, Goldman Sachs, Yahoo
Key takeaway: An excellent problem to visualize the use of the stack operations in problem-solving.
Let’s understand the problem!
Given a stack, write a program to sort the stack in ascending order. We are not allowed to make any assumptions about how the stack is implemented. The only functions to be used are:
- push(s, x): Insert a new element to the stack.
- pop(s): Remove the top element from the stack.
- top(s): Return the top element from the stack.
- isEmpty(s): check whether the stack is empty or not.
Examples
Input Stack: [4, 3, 6, 5, 1, 2] -> top , Output Stack: [1, 2, 3, 4, 5, 6] -> top
Input Stack: [4, 3, 2, 1] ->top, Output Stack: [1, 2, 3, 4] -> top
Discussed solution approaches
- Solution approach 1 : Using a temporary stack
- Solution approach 2 : Using recursion
Solution approach 1: Using a temporary stack
Sorting in an array can be possible in place because we can perform the comparison, shifting, and swapping operations easily using the indexes. But the stack is a LIFO data structure where the first inserted element should be deleted first. The critical question is: can we sort the stack in place? The answer is no because the only way to access or update some intermediate element of a stack is to pop out some other elements, which requires extra space elsewhere. Think!
Now one idea is clear: we need extra space to sort an stack. But the critical question is: why that extra space should be another stack? The answer is simple: during the push and pop operations from one stack to another, we need to maintain the order of elements. Think!
Solution Idea
The solution idea is: we use another stack to maintain the sorted order of the elements. We pop each element from the input stack and push it to the temporary stack one by one till the popped element is greater than the top element of the temporary stack.
When the current element is less than the top element of the temporary stack, we need to find its correct position to insert in the sorted order. For this, we pop all the elements from the temporary stack that are greater than the current element and place them into the input stack. Now we insert the current element into the temporary stack and push back all the previous popped elements from the input stack to the temp stack.
Here is a step by step explanation:
- We create a temporary stack tempStack. Now we run a loop while the input stack is not empty.
- At each iteration, we pop an element from the input stack and compare it with the element present on the top of the tempStack. Initially, tempStack is empty. So in the first iteration, we pop the element from the input stack and push it into the tempStack.
- If tempStack is not empty and the popped element is smaller than the top element of the tempStack, we pop the top element from the tempStack and push it into the input stack. Otherwise, if the element is greater, we push it into the tempStack.
- In other words, we continue the above process in an inner loop until the top of the tempStack is greater than the popped element from the input stack or tempStack is empty.
- The input stack will be empty by the end of the outer loop, and the sorted elements are present in the temporary stack. So we return the tempStack as an output.
Solution Steps
- We create a temporary stack tempStack.
- While the input stack is not empty, we pop an element from the input stack and store it in variable topInputStack.
- While the tempStack is not empty and the top of the tempStack is greater than topInputStack, we pop from the tempStack and push it to the input stack.
- Now we push topInputStack in the tempStack.
- Finally, we return tempStack as a sorted output.
Solution Pseudocode
stack sortStack(stack s)
{
stack tempStack
while (!s.empty())
{
int topInputStack = s.pop()
while (!tempStack.empty() && tempStack.top() > topInputStack)
{
int topTempStack = tempStack.pop()
s.push(topTempStack)
}
tempStack.push(topInputStack)
}
return tempStack
}
Time and space complexity analysis
We pop each element from the tempStack repeatedly to insert a new element. So we need to identify the worst-case scenario for which the above algorithm performs the maximum number of stack operations. Such a scenario occurs when the input stack is sorted in decreasing order. Why? Let's think!
- The top element is the largest. So we need to push and pop this element n times: 1 time during the first iteration and (n-1) times for maintaining the order of remaining (n-1) elements.
- The 2nd element from the top is the 2nd largest element. So we need to push and pop this element n times.
- Similarly, n-2 push and pop operations on the 3rd element, n-3 push, and pop operations on the 4th, etc.
- So in the worst case, total number of stack operations = n + n - 1 + n - 2 + ..... + 1 = n(n+1)/1 = O(n^2). Time Complexity = O(n^2).
Another analysis idea: we need to perform 1 push and pop operation in the 1st iteration, 2 push and pop operations in the 2nd iteration, and so on. In the last iteration, (n-1) sorted elements are present in the tempStack and 1 element in the input stack. So, we need to perform n push and pop operations to place the remaining element from the input stack to the tempStack in the sorted order.
Space complexity = O(n) as we are using a tempStack to store the sorted elements.
Solution approach 2: Using recursion
Solution Idea
This idea is similar to the recursive insertion sort, where we pop the top element from the stack and sort the remaining (n-1) size stack recursively using the same function. After sorting the (n-1) size stack, we use another helper function insertTop(s, topElement), to insert the top element into the current position of the sorted stack.
Implementation of the insertTop(s, topElement) function
- If the stack is empty or topElement is greater than the top, we push it into the stack and return.
- Otherwise, we insert the topElement into the correct position of the sorted stack. For this, we recursively pop out each stack element and call the same function to insert the elements again in the stack in sorted order.
Solution Pseudocode
void insertTop(stack s, int topElement)
{
if (isEmpty(s) || topElement > s.top()))
{
s.push(topElement)
return
}
int temp = s.pop()
insertTop(s, topElement)
s.push(temp)
}
void sortStack(stack s)
{
if (!isEmpty(s))
{
int topElement = s.pop()
sortStack(s)
insertTop(s, topElement)
}
}
Time and space complexity analysis
We are solving the sorting problem of size n by recursively solving the sorting problem of size n-1 and inserting the top element into the n-1 size sorted stack. In the worst case, the time complexity of inserting the top element would be O(n). Think!
Recurrence relation: T(n) = T(n-1) + O(n). This is similar to the recurrence relation of recursive insertion sort or the worst-case time complexity of the quicksort. So time complexity = O(n^2)
This algorithm will use the recursion call stack of size O(n) to maintain the sorted order of input. Space complexity = O(n)
Critical ideas to think!
- How do we modify the above code to sort the stack in descending order?
- Can we solve this problem using some other approach?
- Can we optimize the time complexity of the above approach if we know that the input stack is partially sorted or if there are O(n) inversions?
- What would be the best and average-case time complexity of the above approaches?
- In the second approach, can we use another stack to implement the insertTop() function iteratively instead of using recursion?
Suggested coding questions to practice
