Sort a Stack using Another Stack

Difficulty: Medium, Asked-in: Amazon, Microsoft, Goldman Sachs, Yahoo.

Key takeaway: An excellent problem to visualise 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, 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

• Using a temporary stack 
• Using recursion 

Sorting stack using a temporary stack

A stack is a LIFO (last-in, first-out) data structure, where the last element inserted is the first one 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 without first popping the elements above it. So we need extra space to store the popped elements. Why should that extra space be another stack? An extra stack helps us maintain the order of elements during push and pop operations.

Solution idea

We move elements from the input stack to a temporary stack until we find an element x that is smaller than the top of the temporary stack. To insert x in sorted order, we move every larger element from the temporary stack back to the input stack. Then we push x onto the temporary stack. This places x above all smaller elements and below all larger ones.

Solution steps

1. We create a temporary stack. 

2. We run a outer 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 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 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 pseudocode

sortStack(inputStack)
    create an empty temporary stack tempStack

    while inputStack is not empty
        currentElement = top of inputStack
        pop inputStack
        // Move larger elements back until currentElement
        // can be placed in sorted order.
        while tempStack is not empty and top of tempStack > currentElement
            move top of tempStack to inputStack

        push currentElement onto tempStack

    // Move the sorted elements back to inputStack.
    while tempStack is not empty
        move top of tempStack to inputStack

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: When the input stack is sorted in decreasing order, 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.

Sorting stack using recursion 

Solution idea

This idea is: 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 in the sorted stack.

Implementation of the insertTop(s, topElement): 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 pseudocode

insertTop(s, topElement)
    if s is empty or topElement < top of s
        push topElement onto s
        return

    temp = top of s
    pop s
    insertTop(s, topElement)
    push temp onto s

sortStack(s)
    if s is not empty
        topElement = top of s
        pop s

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

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