Sources: leetcode 75

Rating: medium

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. Here, we will use the integers `0`

, `1`

, and `2`

to represent the color red, white, and blue respectively.

- Solve without using a sort library.
- Sort in single-pass algorithm using constant space.

def sortColors(nums: List[int]) -> None:
# Do not return anything, modify nums in-place instead.

**Solution**

This is the so-called Dutch flag problem. The solution splits the array into three groupings, iterating through using three indices **l**, **m**, **h**, exchanging elements at the indices to ensure that each element ends up in the right groupings.

def sortColors(nums):
l, m, h = 0, 0, len(nums) - 1
while m <= h:
# exchange elements

If the element at **m** is equal to the first value, then it must be exchanged for an element at **l**.

def sortColors(nums):
l, m, h = 0, 0, len(nums) - 1
while m <= h:
if nums[m] == 0:
nums[m], nums[l] = nums[l], nums[m]
l += 1
m += 1
# exchange elements

If the element at **m** is the second value, then it is in the **m** grouping and the index advances.

def sortColors(nums):
l, m, h = 0, 0, len(nums) - 1
while m <= h:
if nums[m] == 0:
nums[m], nums[l] = nums[l], nums[m]
l += 1
m += 1
elif nums[m] == 1:
m += 1
# exchange elements

Otherwise, **m** is the third value, and must be exchanged with an element in the **h** grouping, and **h** updates.

**Final Code**

def sortColors(nums):
l, m, h = 0, 0, len(nums) - 1
while m <= h:
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[h] = nums[h], nums[m]
h -= 1

### Like this:

Like Loading...

*Related*