# 75. Sort Colors     ## Approach 1: 3 pointers

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: void sortColors(vector& nums) { int zero = -1; int one = -1; int two = -1; for (const int num : nums) if (num == 0) { nums[++two] = 2; nums[++one] = 1; nums[++zero] = 0; } else if (num == 1) { nums[++two] = 2; nums[++one] = 1; } else { nums[++two] = 2; } } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public void sortColors(int[] nums) { int zero = -1; int one = -1; int two = -1; for (final int num : nums) if (num == 0) { nums[++two] = 2; nums[++one] = 1; nums[++zero] = 0; } else if (num == 1) { nums[++two] = 2; nums[++one] = 1; } else { nums[++two] = 2; } } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution: def sortColors(self, nums: List[int]) -> None: zero = -1 one = -1 two = -1 for num in nums: if num == 0: two += 1 one += 1 zero += 1 nums[two] = 2 nums[one] = 1 nums[zero] = 0 elif num == 1: two += 1 one += 1 nums[two] = 2 nums[one] = 1 else: two += 1 nums[two] = 2 

## Approach 2: 2 pointers + swapping

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: void sortColors(vector& nums) { int l = 0; // next 0 should be put in l int r = nums.size() - 1; // next 2 should be put in r for (int i = 0; i <= r;) if (nums[i] == 0) swap(nums[i++], nums[l++]); else if (nums[i] == 1) ++i; else // we may swap a 0 to index i, but we're still not sure whether // this 0 is put in the correct index, so we can't move pointer i swap(nums[i], nums[r--]); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public void sortColors(int[] nums) { int l = 0; // next 0 should be put in l int r = nums.length - 1; // next 2 should be put in r for (int i = 0; i <= r;) if (nums[i] == 0) swap(nums, i++, l++); else if (nums[i] == 1) ++i; else // we may swap a 0 to index i, but we're still not sure whether // this 0 is put in the correct index, so we can't move pointer i swap(nums, i, r--); } private void swap(int[] nums, int i, int j) { final int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def sortColors(self, nums: List[int]) -> None: l = 0 # next 0 should be put in l r = len(nums) - 1 # next 2 should be put in r i = 0 while i <= r: if nums[i] == 0: nums[i], nums[l] = nums[l], nums[i] i += 1 l += 1 elif nums[i] == 1: i += 1 else: # we may swap a 0 to index i, but we're still not sure whether # this 0 is put in the correct index, so we can't move pointer i nums[i], nums[r] = nums[r], nums[i] r -= 1