Problem

Sort items using insertion sort with stacks.

Examples

Example 1:

1
2

Input: stack = [4,2,3,1]
Output: [1, 2, 3, 4]

Solution

Method 1 - Using two stacks

Here is the approach:

  • Use the original stack to hold items in two sections: sorted (bottom) and unsorted (top).
  • Utilize a temporary stack to help in repositioning items.
  • Process each item by selecting the top of the original stack, moving unsorted items to the temporary stack, placing the item in its proper position in the sorted section, and then moving items back from the temporary stack to the original stack.

To summarize:

  1. Start with all items in the unsorted section of the original stack.
  2. For each item, remove it from the stack, find its proper position in the sorted section, and place it there.
  3. Use the temporary stack to manage intermediate steps.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Solution {

    public static void insertionSortStack(Stack<Integer> items) {
        Stack<Integer> tempStack = new Stack<>();
        int numItems = items.size();

        for (int i = 0; i < numItems; i++) {
            // Take the next item to be sorted
            int nextItem = items.pop();

            // Move all unsorted items to the temporary stack
            for (int j = 0; j < numItems - i - 1; j++) {
                tempStack.push(items.pop());
            }

            // Move sorted items until finding the correct position for nextItem
            while (!items.isEmpty() && items.peek() > nextItem) {
                tempStack.push(items.pop());
            }

            // Insert the next item in its correct place in sorted section
            items.push(nextItem);

            // Move items back from tempStack to the original stack
            while (!tempStack.isEmpty()) {
                items.push(tempStack.pop());
            }
        }
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(4);
        stack.push(2);
        stack.push(3);
        stack.push(1);

        System.out.println("Original stack: " + stack);
        insertionSortStack(stack);
        System.out.println("Sorted stack: " + stack);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
    def insertionSortStack(self, stack: List[int]) -> List[int]:
        temp_stack: List[int] = []
        num_items = len(stack)

        for i in range(num_items):
            # Take the next item to be sorted
            next_item = stack.pop()

            # Move all unsorted items to the temporary stack
            for _ in range(num_items - i - 1):
                temp_stack.append(stack.pop())

            # Move sorted items until finding the correct position for next_item
            while stack and stack[-1] > next_item:
                temp_stack.append(stack.pop())

            # Insert the next item in its correct place in sorted section
            stack.append(next_item)

            # Move items back from temp_stack to the original stack
            while temp_stack:
                stack.append(temp_stack.pop())

        return stack

# Test the implementation
sol = Solution()
stack = [4, 2, 3, 1]
print("Original stack:", stack)
sorted_stack = sol.insertionSortStack(stack)
print("Sorted stack:", sorted_stack)

Complexity

  • ⏰ Time complexity: O(n^2) due to the repeated repositioning of elements within the stacks.
  • 🧺 Space complexity: O(n) because of the additional temporary stack.