Sort Colors

# Approach 1: Counting sort — O(n) time, O(1) space, two passes
def sort_colors_counting(nums: list[int]) -> None:
    counts = [0] * 3
    for n in nums:
        counts[n] += 1

    i = 0
    for val in range(3):
        for _ in range(counts[val]):
            nums[i] = val
            i += 1


# Approach 2: Dutch National Flag — O(n) time, O(1) space, ONE pass
def sort_colors(nums: list[int]) -> None:
    lo, mid, hi = 0, 0, len(nums) - 1
    while mid <= hi:
        if nums[mid] == 0:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo += 1
            mid += 1
        elif nums[mid] == 2:
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi -= 1  # don't advance mid — swapped value needs checking
        else:
            mid += 1


if __name__ == '__main__':
    nums = [2, 0, 2, 1, 1, 0]
    sort_colors(nums)
    print(nums)  # [0, 0, 1, 1, 2, 2]