Sort a Stack using Another Stack or using Recursion

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. To implement this, we need to use following stack operations:

• 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.

Example 1

Input stack: [4, 3, 6, 5, 1, 2] -> top, Output stack: [6, 5, 4, 3, 2, 1] -> top

Example 2

Input stack: [4, 3, 2, 1] ->top, Output stack: [4, 3, 2, 1] -> top

Example 3

Input stack: [5, 2, 8, 1, 9] ->top, Output stack: [9, 8, 5, 2, 1] -> top

Discussed solution approaches

• Solution approach 1: Using a temporary stack 
• Solution approach 2: Using recursion 

Solution approach 1: Sorting stack using a temporary stack

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.

Solution idea

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.

Solution steps

1. We create a temporary stack. 

2. 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.

   • If the temporary stack is empty or the currentElement is greater than the top element of the temporary stack, we push the currentElement into the temporary stack.
   • Otherwise, we run an inner while loop until currentElement is greater than the top element. At each iteration, we pop the top element from the temporary stack and push it back into the input stack. By the end of this inner loop, we will find the correct place to insert currentElement in the sorted order. So we push currentElement into the temporary stack.
3. By the end of the outer while loop, the input stack will be empty, and the sorted elements (in decreasing order) will be present in the temporary stack. So, we copy the elements from the temporary stack back to the input stack to sort the elements in increasing order.

Solution code C++

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();
    }
}

Solution code Python

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())

Solution code Java

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());
    }
}

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. If we observe, such a scenario will occur 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 2n - 1 times: 1 time during the first iteration and 2(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 2n - 3 times. Similarly, 2n - 5 push and pop operations on the 3rd element, 2n - 7 push and pop operations on the 4th, etc.
• So in the worst case, the total number of stack operations = (2n - 1) + (2n - 3) + (2n - 5) + .... + 1 = 2 [(n - 1) + (n - 2) + ... + 1] - (1 + 1 +.... n times) = 2[n(n -1)/2] - n = n^2 - n - n = n^2 - 2n = O(n^2). Time complexity = O(n^2).

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.

Solution approach 2: Sorting stack 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 less 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 code C++

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);
    }
}

Solution code Python

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)

Solution code Java

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);
        }
    }
}

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

• Implement a stack using queue
• Implement a queue using stack
• Reverse a stack using another stack
• Reverse a queue using another queue
• Check if the two given stacks are the same
• Min-stack problem
• Implement Stack and Queue using Deque
• Implement stack using a priority queue
• Find maximum in a stack

Enjoy learning, Enjoy Algorithms