75. Sort Colors

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