Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Sorting a Stack
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a stack, sort it using only stack operations (push and pop).

You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array). The values in the stack are to be sorted in descending order, with the largest elements on top.

Examples

1. Input: [34, 3, 31, 98, 92, 23]
   Output: [3, 23, 31, 34, 92, 98]

2. Input: [4, 3, 2, 10, 12, 1, 5, 6]
   Output: [1, 2, 3, 4, 5, 6, 10, 12]

3. Input: [20, 10, -5, -1]
   Output: [-5, -1, 10, 20]

Solution

This problem can be solved by using a temporary stack as auxiliary storage. The algorithm takes an input stack and sorts it using a temporary stack tmpStack. The sorting process is done by continuously popping elements from the input stack and pushing them onto the tmpStack in sorted order, rearranging elements as necessary between the stacks until the original stack is empty.

This algorithm leverages the LIFO (last in, first out) nature of a stack. It removes elements from the original stack one by one and uses a second stack to keep the elements sorted. If the top element of the sorted stack is larger than the current element, it moves the larger elements back to the original stack until it finds the correct spot for the current element, at which point it pushes the current element onto the sorted stack. Because of this, the smaller elements end up at the bottom of the sorted stack and the largest element on the top, resulting in a stack sorted in descending order from top to bottom.

Step-by-Step Algorithm

  1. The sort method receives an input stack.

  2. It initializes an empty temporary stack tmpStack.

  3. The algorithm enters a loop that continues until the input stack is empty.

  4. In each iteration, it pops the top element (tmp) from the input stack.

  5. Then it enters another loop, which continues as long as tmpStack is not empty and the top of tmpStack is larger than tmp. In each iteration of this inner loop, it pops the top element from tmpStack and pushes it back onto the input stack.

  6. After the inner loop ends, it pushes tmp onto tmpStack. The inner loop ensures that tmpStack is always sorted in descending order, with smaller elements at the bottom and larger elements at the top, and tmp is placed into its correct position in this order.

  7. Once the outer loop ends and the input stack is empty, tmpStack contains all the elements originally in the input stack but sorted in descending order.

  8. It then returns tmpStack.

Algorithm Walkthrough

  1. Initial Setup:

    • Input Stack (top to bottom): [34, 3, 31, 98, 92, 23]
    • Temporary Stack (tmpStack): Empty
  2. Process Element: 23

    • Pop 23 from the input stack.
    • tmpStack is empty, so push 23 onto tmpStack.
    • Input Stack: [34, 3, 31, 98, 92], tmpStack: [23]
  3. Process Element: 92

    • Pop 92 from the input stack.
    • Since 23 < 92, push 92 onto tmpStack.
    • Input Stack: [34, 3, 31, 98], tmpStack: [23, 92]
  4. Process Element: 98

    • Pop 98 from the input stack.
    • Since 92 < 98, push 98 onto tmpStack.
    • Input Stack: [34, 3, 31], tmpStack: [23, 92, 98]
  5. Process Element: 31

    • Pop 31 from the input stack.
    • Move elements from tmpStack to input stack until the correct position for 31 is found.
    • Pop 98, then 92 from tmpStack and push them onto the input stack.
    • Push 31 onto tmpStack.
    • Input Stack: [34, 3, 98, 92], tmpStack: [23, 31]
    • In next 2 iterations, pop 98, and 92 from input stack and push back to the tmpStack. Updated stack will be: Input Stack: [34, 3], tmpStack: [23, 31, 92, 98].
  6. Process Element: 3

    • Pop 3 from the input stack.
    • Move elements from tmpStack to input stack until the correct position for 3 is found.
    • Pop 98, 92, 31, then 23 from tmpStack and push them onto the input stack.
    • Push 3 onto tmpStack.
    • Input Stack: [34, 98, 92, 31, 23], tmpStack: [3]
      • In next 4 iterations, pop 98, 92, 31, and 23 from the input stack and push back to the tmpStack. Updated stack will be: Input Stack: [34], tmpStack: [3, 23, 31, 92, 98].
  7. Process Element: 34

    • Pop 34 from the input stack.
    • Move elements from tmpStack to input stack until the correct position for 34 is found.
    • Pop 98, then 92 from tmpStack and push them onto the input stack.
    • Push 34 onto tmpStack.
    • Input Stack: [98, 92], tmpStack: [3, 23, 31, 34].
    • In next 2 iterations, pop 98, and 92 from the input stack and push to the tmpStack.
  8. Final Result:

    • Input Stack: Empty
    • tmpStack (Sorted, top to bottom): [3, 23, 31, 34, 92, 98]

Here is the visual representation of the algorithm:

mediaLink

1 of 15

Code

Here is the code for this algorithm:

Python3
Python3

. . . .

Complexity Analysis

Time Complexity

  • Outer while loop: The outer loop runs until the input stack is empty. If the input stack has N elements, each element is popped from the input stack exactly once and pushed onto the temporary stack.

  • Inner while loop: In the worst case, the inner loop runs for each element that is being popped from the input stack. If the elements in the input stack are in descending order, every element in tmpStack needs to be popped and then pushed back. Thus, for each of the N elements, we may have to move several elements between the stacks, leading to a quadratic time complexity.

Overall time complexity: O(N^2), where N is the number of elements in the input stack.

Space Complexity

  • Temporary stack: The algorithm uses an additional temporary stack, tmpStack, to hold the sorted elements. The space required by this stack is proportional to the number of elements in the input stack, O(N).

  • Input stack: The input stack itself uses space O(N), but since this is part of the input and we are not creating a new copy, it is not considered extra space.

  • Other variables: The algorithm uses a few extra variables (e.g., tmp), which take constant space, O(1).

Overall space complexity: O(N).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible