Lecture Notes: Sorting Colors Algorithm

Problem Introduction

• Task: Sort an array of integers (nums) with values 0, 1, or 2 in ascending order.
• Constraint: Sort in place without using a library sorting function.
• Goal: Achieve linear time complexity O(n) and constant space complexity O(1).

Trivial Solution

• Library Sorting: Using built-in sort (disallowed, O(n log n) complexity).
• Custom Sorting: Implement sorting algorithms (e.g., Merge Sort, Quick Sort) - same O(n log n) complexity.

Optimized Solution 1: Bucket Sort

• Bucket Sort explained:
  • Only three values: 0, 1, and 2.
  • Use extra memory (hashmap or array of size 3).
  • Scan input array and count occurrences of each value.
  • Construct sorted output without creating a new array using counted values.
• Steps:
  1. Create counts for 0, 1, and 2.
  2. Overwrite original array using counts: zeros first, then ones, then twos.
• Complexity: O(n) time, O(1) space for array of size 3.

Optimized Solution 2: Single-Pass with Partitioning

• Inspired by the Quicksort Partition method.

• Pointers:

  • left: Marks the boundary for zeros.
  • right: Marks the boundary for twos.
  • i: Iterates through the array.

• Procedure:

  1. Zeros at Left: Any time you encounter 0, swap it to the position marked by left and increment left.
  2. Twos at Right: Any time you encounter 2, swap it with right and decrement right.
  3. Ones Ignore: Skip ones, they remain in the middle.
  4. i Management: Increment i unless you performed a swap with right (to check the swapped value).

• Edge Cases: Swapping might bring a zero in the middle; hence the increment logic.

Implementation Details

• Function signature: sortColors(nums) function containing helper swap(i, j) function for swapping.
• Manage three pointers and iterate through the array appropriately to ensure correct in-place sorting.

Example Walkthrough

1. Initialize pointers left and right, with i traversing the array.
2. Adjust left and right pointers based on the current value of nums[i].
3. Stop when i surpasses right as remaining elements will already be sorted (all twos after right).
4. Efficiently achieve in-place sort maintaining linear run-time.

Example Code

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        def swap(i, j):
            nums[i], nums[j] = nums[j], nums[i]
        left, right = 0, len(nums) - 1
        i = 0
        while i <= right:
            if nums[i] == 0:
                swap(i, left)
                left += 1
            elif nums[i] == 2:
                swap(i, right)
                right -= 1
                i -= 1 # Decrement i to revisit this index in next iteration.
            i += 1

Conclusion

• Two main approaches were discussed for sorting an array of three distinct values: Bucket Sort and Single-Pass Partitioning.
• Emphasis on achieving an efficient O(n) time complexity and O(1) space complexity.
• Single-Pass Partitioning is not only space-efficient but also handles the task elegantly using three pointers.
• Practical code implementation provided for better understanding.