title: Sort Colors
slug: sort-colors
difficulty: medium
leetcode_id: 75
leetcode_url: https://leetcode.com/problems/sort-colors/
categories:
  - arrays
  - two-pointers
  - sorting
patterns:
  - slug: two-pointers
    is_optimal: true

function_signature: "def sort_colors(nums: list[int]) -> None:"

test_cases:
  visible:
    - input: { nums: [2, 0, 2, 1, 1, 0] }
      expected: [0, 0, 1, 1, 2, 2]
    - input: { nums: [2, 0, 1] }
      expected: [0, 1, 2]
  hidden:
    - input: { nums: [0] }
      expected: [0]
    - input: { nums: [1, 0] }
      expected: [0, 1]
    - input: { nums: [2, 2, 2, 1, 1, 0, 0] }
      expected: [0, 0, 1, 1, 2, 2, 2]
    - input: { nums: [1, 2, 0] }
      expected: [0, 1, 2]

description: |
  Given an array `nums` with `n` objects colored red, white, or blue, sort them **in-place** so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

  We will use the integers `0`, `1`, and `2` to represent the color red, white, and blue, respectively.

  You must solve this problem without using the library's sort function.

constraints: |
  - `n == nums.length`
  - `1 <= n <= 300`
  - `nums[i]` is either `0`, `1`, or `2`

examples:
  - input: "nums = [2,0,2,1,1,0]"
    output: "[0,0,1,1,2,2]"
    explanation: "The array is sorted in-place so all 0s come first, then all 1s, then all 2s."
  - input: "nums = [2,0,1]"
    output: "[0,1,2]"
    explanation: "Each color appears exactly once, sorted in the correct order."

explanation:
  intuition: |
    Imagine you have a deck of cards in three colours: red, white, and blue, all shuffled together. Your task is to arrange them so all reds are on the left, all whites in the middle, and all blues on the right — without using any extra piles.

    The key insight is that we can **partition the array into three regions** using just two boundaries. Think of it like having two "sweepers" that push elements to their correct regions:

    - Everything before the left boundary is **red (0)**
    - Everything after the right boundary is **blue (2)**
    - Everything in between is either **white (1)** or **unsorted**

    As we scan through the array with a current pointer, we make decisions:
    - See a red? Swap it to the left region and expand that region
    - See a blue? Swap it to the right region and shrink that region
    - See a white? Leave it and move on

    This is known as the **Dutch National Flag** algorithm, named by Edsger Dijkstra because the Dutch flag has three horizontal stripes (red, white, blue).

  approach: |
    We solve this using the **Dutch National Flag (Three-Way Partitioning)** algorithm:

    **Step 1: Initialise three pointers**

    - `low`: Points to the boundary of the red region (starts at index `0`)
    - `mid`: The current element being examined (starts at index `0`)
    - `high`: Points to the boundary of the blue region (starts at index `n - 1`)

    &nbsp;

    **Step 2: Process elements while `mid <= high`**

    - If `nums[mid] == 0` (red): Swap `nums[low]` and `nums[mid]`, increment both `low` and `mid`
    - If `nums[mid] == 1` (white): Just increment `mid` — it's already in the correct region
    - If `nums[mid] == 2` (blue): Swap `nums[mid]` and `nums[high]`, decrement `high` only (don't increment `mid` because the swapped element needs to be checked)

    &nbsp;

    **Step 3: Termination**

    - When `mid > high`, all elements have been processed
    - The array is now partitioned: `[0...0, 1...1, 2...2]`

    &nbsp;

    The reason we don't increment `mid` after swapping with `high` is that we don't know what value came from the right side — it could be `0`, `1`, or `2`, so we need to examine it on the next iteration.

  common_pitfalls:
    - title: Incrementing mid After Swapping with high
      description: |
        When you swap `nums[mid]` with `nums[high]`, the element that comes from position `high` is unknown — it hasn't been examined yet.

        If you increment `mid` after this swap, you might skip over a `0` that should be moved to the left region.

        For example, with `[2, 0, 1]`: swapping index 0 with index 2 gives `[1, 0, 2]`. If you increment `mid`, you'd move to index 1, but the `1` at index 0 is already correct by luck — in other cases, the swapped-in value could be `0` and need further processing.
      wrong_approach: "Always increment mid after every swap"
      correct_approach: "Only increment mid when swapping with low or when current element is 1"

    - title: Using Extra Space
      description: |
        A common first approach is to count the occurrences of each colour and then overwrite the array in two passes:

        1. Count: `count0`, `count1`, `count2`
        2. Fill: write `count0` zeros, then `count1` ones, then `count2` twos

        While this works and is O(n) time, the follow-up asks for a **one-pass** solution. The Dutch National Flag algorithm achieves this in a single traversal.
      wrong_approach: "Two-pass counting approach"
      correct_approach: "Single-pass three-way partitioning"

    - title: Off-by-One in Loop Condition
      description: |
        The loop should continue while `mid <= high`, not `mid < high`.

        When `mid == high`, there's still one element that hasn't been classified. If you use `mid < high`, you might leave the last element in the wrong position.

        For example, with `[0, 1, 2]` where `low = 0`, `mid = 2`, `high = 2`: the element at index 2 still needs to be verified (even though it's already correct in this case).
      wrong_approach: "while mid < high"
      correct_approach: "while mid <= high"

  key_takeaways:
    - "**Three-way partitioning**: Use two boundaries to divide an array into three regions — a powerful technique for problems with three distinct values"
    - "**Dutch National Flag**: Named by Dijkstra, this algorithm is the foundation for quicksort's partition step with duplicate elements"
    - "**Pointer movement asymmetry**: When swapping with the left boundary, we know the swapped element is `1` (already examined). When swapping with the right, we don't — hence the different increment behaviour"
    - "**In-place sorting**: Achieves O(1) space by using swap operations rather than auxiliary arrays"

  time_complexity: "O(n). Each element is examined at most twice — once when `mid` reaches it, and possibly once more if it was swapped from the right side."
  space_complexity: "O(1). We only use three pointer variables (`low`, `mid`, `high`) regardless of input size."

solutions:
  - approach_name: Dutch National Flag
    is_optimal: true
    code: |
      def sort_colors(nums: list[int]) -> None:
          """
          Sorts the array in-place using three-way partitioning.
          Do not return anything, modify nums in-place instead.
          """
          # Pointers for the three regions
          low = 0           # Boundary for red (0s)
          mid = 0           # Current element being examined
          high = len(nums) - 1  # Boundary for blue (2s)

          while mid <= high:
              if nums[mid] == 0:
                  # Red: swap to the left region
                  nums[low], nums[mid] = nums[mid], nums[low]
                  low += 1
                  mid += 1
              elif nums[mid] == 1:
                  # White: already in correct region, just move on
                  mid += 1
              else:
                  # Blue (nums[mid] == 2): swap to the right region
                  nums[mid], nums[high] = nums[high], nums[mid]
                  high -= 1
                  # Don't increment mid — need to examine the swapped element
    explanation: |
      **Time Complexity:** O(n) — Each element is visited at most twice.

      **Space Complexity:** O(1) — Only three pointer variables used.

      The algorithm maintains three regions: `[0, low)` contains 0s, `[low, mid)` contains 1s, and `(high, n-1]` contains 2s. The region `[mid, high]` is unsorted. We process until `mid` crosses `high`.

  - approach_name: Counting Sort
    is_optimal: false
    code: |
      def sort_colors(nums: list[int]) -> None:
          """
          Two-pass approach: count then fill.
          Do not return anything, modify nums in-place instead.
          """
          # First pass: count occurrences
          count0 = count1 = count2 = 0
          for num in nums:
              if num == 0:
                  count0 += 1
              elif num == 1:
                  count1 += 1
              else:
                  count2 += 1

          # Second pass: overwrite array
          idx = 0
          for _ in range(count0):
              nums[idx] = 0
              idx += 1
          for _ in range(count1):
              nums[idx] = 1
              idx += 1
          for _ in range(count2):
              nums[idx] = 2
              idx += 1
    explanation: |
      **Time Complexity:** O(n) — Two passes through the array.

      **Space Complexity:** O(1) — Only three counter variables.

      This approach counts each colour in the first pass, then overwrites the array in the second pass. While it achieves the same time and space complexity as the Dutch National Flag, it requires two passes. The follow-up explicitly asks for a one-pass solution.
