Array is composed by only 3 types of elements. Sort it fast.

Similar Problems:

- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #twopointer, #array

Given an array with n objects colored red, white or blue, sort them 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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## https://code.dennyzhang.com/sort-colors ## Basic Ideas: two pointer ## ## [2,0,2,1,1,0,1] ## [1,0,2,1,1,0,2] ## Complexity: Time O(n), Space O(1) class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) if n == 0: return left, right = 0, n-1 cur = 0 while cur <= right: if nums[cur] == 0: # swap with left. # we know nums[left] won't be 2, so move cur nums[left], nums[cur] = nums[cur], nums[left] left, cur = left+1, cur+1 elif nums[cur] == 2: # swap with right. # we don't know whether nums[right] would be 2 as well # So we can't move cur nums[right], nums[cur] = nums[cur], nums[right] right -= 1 else: # value as 1 cur += 1