Given an array withnobjects colored red, white or blue, sort themin-placeso 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.Note:You are not suppose to use the library's sort function for this problem.Example:Input:[2,0,2,1,1,0]Output:[0,0,1,1,2,2]

This is known as a Dutch national flag problem – there are three colours in the flag of Netherlands: red, white, and blue, and given balls in these colours, the task is to sort these balls in the order of red, white, and blue. (Wikipedia) One of the potential applications of this problem is to develop a variant of `partition()`

function in the quicksort algorithm.

The brute force solution could using a two-pass algorithm: use the first scanning to count the number of each colour and, for the second iterations, overwrite the colours according to their counts.

However, we are able to solve it with one-pass. We can initiate three pointers with `i`

indicating the beginning of white balls, `cur`

indicating the current position in the iteration, and `j`

referring to the end of white balls. While iterating, once `cur`

comes across a red ball, we can swap it with `i`

, and `i+=1`

; or if `cur`

comes across a blue ball, we can swap it with `j`

, and `j-=1`

; or if `cur`

comes across a white ball, it would simply move forward.

```
class Solution:
def sortColors(self, nums: List[int]) -> None:
i, cur, j = 0,0,len(nums)-1
while cur <= j:
if nums[cur] == 0:
nums[i],nums[cur] = nums[cur],nums[i]
cur += 1
i += 1
elif nums[cur] == 2:
nums[j],nums[cur] = nums[cur],nums[j]
j -= 1
else:
cur += 1
```

To provide a better explanation, I will also attach its pseudocode from Wikipedia:

```
procedure three-way-partition(A : array of values, mid : value):
i ← 0
j ← 0
k ← size of A
while j < k:
if A[j] < mid:
swap A[i] and A[j]
i ← i + 1
j ← j + 1
else if A[j] > mid:
k ← k - 1
swap A[j] and A[k]
else:
j ← j + 1
```