75. Sort Colors

Updated: 2024-03-12
1 min read

On This Page

LeetCode problem

This problem is also known as the Dutch National Flag problem. One solution is to use three pointers to partition the array into three sections: red, white, and blue.

Here’s the algorithm:

  1. Initialize three pointers: left, mid, and right.
  2. Initialize left to 0, mid to 0, and right to n-1, where n is the length of the input array.
  3. While mid is less than or equal to right:
    • If nums[mid] is 0, swap nums[mid] with nums[left], increment mid and left.
    • If nums[mid] is 1, increment mid.
    • If nums[mid] is 2, swap nums[mid] with nums[right], decrement right.
  4. Return the sorted array.
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        l, m, r = 0, 0, len(nums) - 1
        while m <= r:
            if nums[m] == 0:
                nums[m], nums[l] = nums[l], nums[m]
                l += 1
                m += 1
            elif nums[m] == 1:
                m += 1
            else:
                nums[m], nums[r] = nums[r], nums[m]
                r -= 1