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.
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. To implement this, we need to use following stack operations:
Input stack: [4, 3, 6, 5, 1, 2] -> top, Output stack: [6, 5, 4, 3, 2, 1] -> top
Input stack: [4, 3, 2, 1] ->top, Output stack: [4, 3, 2, 1] -> top
Input stack: [5, 2, 8, 1, 9] ->top, Output stack: [9, 8, 5, 2, 1] -> top
A stack is a LIFO (Last-In, First-Out) data structure, where the last inserted element is the first one to be removed. The critical question is: Can we sort a stack in place? The answer is no because we cannot directly access or insert an element at an intermediate position within a stack without first popping out elements before that position. So, we would need additional space to store all the elements that need to be popped out. Think!
One idea is clear: We need extra space to sort an stack. Now the critical question is: Why that extra space should be another stack? The answer is simple: Another extra stack will help us to maintain the order of elements during the push and pop operations.
We pop each element from the input stack and push it onto the temporary stack until we find an element, 'x,' that is smaller than the top element of the temporary stack. Now, we need to determine the correct position in the temporary stack to insert element 'x' in sorted order.
To achieve this, we pop all elements from the temporary stack that are greater than 'x' and place them back into the input stack. Then, we insert element 'x' into the temporary stack and push back all the previously popped elements from the input stack into the temporary stack.
We run an outer while loop until input stack is empty. At each iteration: We pop an element from the input stack and store it in a variable currentElement.
void sortStack(stack<int>& inputStack)
{
stack<int> tempStack;
while (inputStack.empty() == false)
{
int currentElement = inputStack.top();
inputStack.pop();
// Find the correct position in the temporary stack to insert the element
while (tempStack.empty() == false && tempStack.top() > currentElement)
{
inputStack.push(tempStack.top());
tempStack.pop();
}
tempStack.push(currentElement);
}
while (tempStack.empty() == false)
{
inputStack.push(tempStack.top());
tempStack.pop();
}
}
def sortStack(inputStack):
tempStack = []
while inputStack:
currentElement = inputStack.pop()
# Find the correct position in the temporary stack to insert the element
while tempStack and tempStack[-1] > currentElement:
inputStack.append(tempStack.pop())
tempStack.append(currentElement)
while tempStack:
inputStack.append(tempStack.pop())
public class Solution
{
public void sortStack(Stack<Integer> inputStack)
{
Stack<Integer> tempStack = new Stack<>();
while (!inputStack.empty())
{
int currentElement = inputStack.pop();
while (!tempStack.empty() && tempStack.peek() > currentElement)
inputStack.push(tempStack.pop());
tempStack.push(currentElement);
}
while (!tempStack.empty())
inputStack.push(tempStack.pop());
}
}
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. If we observe, such a scenario will occur when the input stack is sorted in decreasing order. Why? Let's think!
Another analysis idea: We need to perform 1 push and pop operation in the 1st iteration, 3 push and pop operations in the 2nd iteration, 5 push and pop operations in the 3rd 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 2(n - 1) + 1 push and pop operations to place the remaining element to the tempStack in the sorted order.
Space complexity = O(n) as we are using a tempStack to store the sorted elements.
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
void insertTop(stack<int>& s, int topElement)
{
if (s.empty() || topElement < s.top())
{
s.push(topElement);
return;
}
int temp = s.top();
s.pop();
insertTop(s, topElement);
s.push(temp);
}
void sortStack(stack<int>& s)
{
if (!s.empty())
{
int topElement = s.top();
s.pop();
sortStack(s);
insertTop(s, topElement);
}
}
def insertTop(s, topElement):
if not s or topElement < s[-1]:
s.append(topElement)
return
temp = s.pop()
insertTop(s, topElement)
s.append(temp)
def sortStack(s):
if s:
topElement = s.pop()
sortStack(s)
insertTop(s, topElement)
public class Solution
{
private void insertTop(Stack<Integer> s, int topElement)
{
if (s.empty() || topElement < s.peek())
{
s.push(topElement);
return;
}
int temp = s.pop();
insertTop(s, topElement);
s.push(temp);
}
public void sortStack(Stack<Integer> s)
{
if (!s.empty())
{
int topElement = s.pop();
sortStack(s);
insertTop(s, topElement);
}
}
}
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).
Enjoy learning, Enjoy Algorithms