Sort Colors

01 · Question

Given an array nums with n objects colored red, white, or blue (0, 1, 2), sort them in-place so that objects of the same color are adjacent.

Use the Dutch National Flag algorithm in one pass.

02 · Solution

Reference solution

1def sortColors(nums: List[int]) -> None:
2    l, r = 0, len(nums) - 1
3    i = 0
4    
5    while i <= r:
6        if nums[i] == 0:
7            nums[l], nums[i] = nums[i], nums[l]
8            l += 1
9            i += 1
10        elif nums[i] == 2:
11            nums[r], nums[i] = nums[i], nums[r]
12            r -= 1
13        else:
14            i += 1

Merge Intervals