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. The only functions to be used are:
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
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!
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:
stack<int> sortStack(stack<int> s)
{
stack<int> tempStack;
while (!s.empty())
{
int topInputStack = s.top();
s.pop();
while (!tempStack.empty() && tempStack.top() > topInputStack)
{
int topTempStack = tempStack.top();
tempStack.pop();
s.push(topTempStack);
}
tempStack.push(topInputStack);
}
return tempStack;
}
def sortStack(s):
tempStack = []
while s:
topInputStack = s.pop()
while tempStack and tempStack[-1] > topInputStack:
topTempStack = tempStack.pop()
s.append(topTempStack)
tempStack.append(topInputStack)
return tempStack
public class Solution
{
public Stack<Integer> sortStack(Stack<Integer> s)
{
Stack<Integer> tempStack = new Stack<>();
while (!s.empty())
{
int topInputStack = s.pop();
while (!tempStack.empty() && tempStack.peek() > topInputStack)
{
int topTempStack = tempStack.pop();
s.push(topTempStack);
}
tempStack.push(topInputStack);
}
return tempStack;
}
}
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!
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.
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)