Sort A Stack Using Another Stack

Difficulty: Medium

Asked in: Amazon, Microsoft, VMWare

Understanding the Problem

Problem Description

You are given a stack of integers, write a program to sort it. You could use another stack if needed.

Problem Note

The top of the stack must point to the smallest element.
The stack must be sorted in increasing order from the top of the stack to its bottom.

Example 1

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

Example 2

Input: Top -> [1,2,3]
Output: Top -> [1,2,3]

Example 3

Input: Top -> [10,9,3,1]
Output: Top -> [1,3,9,10]

You can first try to solve this problem here.

Solutions

We will be discussing two different approaches:-

Sorting using another stack
Sorting using recursion

1. Sorting Using Another Stack

A stack performs push and pop operations. So, the push and pop operations are carried out between the input_stack and the auxilary_stack in such a way that the auxiliary stack contains the sorted input stack.

Consider this Example — Consider the input stack is [1, 2, 5, 3, 4]

Element taken out: 1
Input Stack: [2, 5, 3, 4]
Aux Stack: [1]

Element taken out: 4
Input Stack: [2, 5, 3]
Aux Stack: [1, 4]

Element taken out: 3
Input Stack: [2, 5, 4]
Aux Stack: [1]

Element taken out: 3
Input Stack: [2, 5, 4]
Aux Stack: [1, 3]

Element taken out: 4
Input Stack: [2, 5]
Aux Stack: [1, 3, 4]

Element taken out: 5
Input Stack: [2]
Aux Stack: [1, 3, 4, 5]

Element taken out: 2
Input Stack: [5]
Aux Stack: [1, 3, 4]

Element taken out: 2
Input Stack: [5, 4]
Aux Stack: [1, 3]

Element taken out: 2
Input Stack: [5, 4, 3]
Aux Stack: [1]

Element taken out: 2
Input Stack: [5, 4, 3]
Aux Stack: [1, 2]

Element taken out: 3
Input Stack: [5, 4]
Aux Stack: [1, 2, 3]

Element taken out: 4
Input Stack: [5]
Aux Stack: [1, 2, 3, 4]

Element taken out: 5
Input Stack: []
Aux Stack: [1, 2, 3, 4, 5]

Output - [1, 2, 3, 4, 5]

If you will go through this example, you will understand what is happening behind the hood.

Solution Steps

Create a temporary stack say aux_stack .
Repeat until the input_stack is not empty
Pop an element from input_stack call it temp_value.
While aux_stack is not empty and top of the aux_stack < temp_value , pop data from aux_stack and push it to the input_stack
Push temp_value to the aux_stack
return the aux_stack .

Pseudo Code

Stack sort_stack(Stack input_stack) {
    Stack aux_stack
    while(!input_stack.empty())
    {
        int temp_value = input_stack.top()
        input_stack.pop()
        while(!aux_stack.empty() and aux_stack.top() > temp) {
            input_stack.push(aux_stack.top())
            aux_stack.pop()
        }
        aux_stack.push(temp_value)
    }
    return aux_stack
}

Complexity Analysis

Time Complexity: O(n²)

Space Complexity: O(n)

Critical Ideas to Think

Why did we pop from the aux_stack if the top is less than temp?
What changes will you make in this pseudo-code to sort the stack in decreasing order?
What would be the worst-case for this approach?

2. Sort stack using recursion

The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one in sorted order.

Consider this example:

First pop all the elements from the stack and store popped element in variable ‘temp’. After poping all the elements function’s stack frame will look like:

temp = 4   --> stack frame #1
temp = 3   --> stack frame #2
temp = 2   --> stack frame #3
temp = 5   --> stack frame #4
temp = 1   --> stack frame #5

Now stack is empty and ‘insert_in_sorted_order()’ function is called and it inserts 1 (from stack frame #5) at the bottom of the stack. Now stack looks like below:

1    <-- top of the stack

Now next element i.e. 5 (from stack frame #4) is picked. Since 5 > 1, 5 is inserted at the bottom of the stack. Now stack becomes:

1    <-- top of the stack
5

Next 2 (from stack frame #3) is picked. Since 2 > 1, 2 is inserted below 1. Now stack becomes:

1    <-- top of the stack
2    
5

Next 3 (from stack frame #2) is picked. Since 3 > 1 and 3 > 2, it is inserted below 2. Now stack becomes:

1    <-- top of the stack
2
3    
5

Now 4 (from stack frame #1) is picked, as 4 > 1 and 4 > 2 and 4 > 3, it is inserted below 3. Now stack becomes:

1    <-- top of the stack
2
3
4    
5

Solution Steps

Create these two functions →

sort_stack(stack)

If the stack is not empty,

pop the element from the stack and store it in a temp variable
call sort_and_insert(stack, temp)

sort_and_insert(stack, temp)

If the stack is empty or temp < stack.top()
then push temp to the top of the stack otherwise, pop data from the stack and store it in temp2.
call sort_and_insert(stack, temp)
and then push(stack, temp2)

Pseudo Code

// Utility Function
void sort_stack_and_insert(stack s, int data) {
    if (isEmpty(s) or data < s.top()) {
        push(s, data)
        return
    }
    temp = s.pop()
    sort_stack_and_insert(s, data)
    push(s, temp)
}

// Driver function
stack sort_stack(stack s) {
    if (!isEmpty(s))
    {
        int data = s.pop()
        sort_stack(s)
        sort_stack_and_insert(s, data)
    }
    return s
}

Complexity Analysis

Time Complexity: O(n²)

Space Complexity: O(n), due to n stack frames during recursion.

Critical Ideas to Think

Do you think that if you will convert the first approach to recursive from iterative, then both of the approaches become the same?
Do you understand how the stack is being sorted in the recursion tree?