# 75. Sort Colors

Question link is here.

# Question

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.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Example 3:

Input: nums = [0]
Output: [0]

Example 4:

Input: nums = [1]
Output: [1]

# Solution

# Counter

Since there are only three possible values, we can just use a counter to count each element, and modify the array in place.

class Solution {
    public void sortColors(int[] nums) {
        HashMap<Integer, Integer> c = new HashMap<>();
        c.put(0, 0);
        c.put(1, 0);
        c.put(2, 0);
        for(int i = 0; i < nums.length; i++) {
            c.put(nums[i], c.get(nums[i]) + 1);
        }
        int i = 0;
        while (i < c.get(0)) {
            nums[i] = 0;
            i += 1;
        }
        while (i < c.get(0) + c.get(1)) {
            nums[i] = 1;
            i += 1;
        }
        while (i < nums.length) {
            nums[i] = 2;
            i += 1;
        }
    }
}

from collections import Counter
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        c = Counter(nums)
        i = 0
        while i < c[0]:
            nums[i] = 0
            i += 1
        while i < c[0] + c[1]:
            nums[i] = 1
            i += 1
        while i < c[0] + c[1] + c[2]:
            nums[i] = 2
            i += 1

Time Complexity: $O(n)$ .

# Two pointer

In a general way of speaking, we want all the 0's stay at the left of the array, and all the 2's stay at the right of the array, and all the 1's stay in the middle, so we can use two pointer pointing at left and right side of the array, and iterate index i through the array, whenever we encouter a 0, we swap i and left, and whenever we encouter a 2, we swap i and right.

class Solution {
    public void sortColors(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int i = 0;
        while(i <= right) {
            if(nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[left];
                nums[left] = temp;
                i += 1;
                left += 1;
            } else if (nums[i] == 2) {
                int temp = nums[right];
                nums[right] = nums[i];
                nums[i] = temp;
                right -= 1;
            } else {
                i += 1;
            }
        }
        
    }
}

class Solution:
    def sortColors(self, nums) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left = 0
        right = len(nums) - 1
        i = 0
        while i <= right:
            if nums[i] == 0:
                nums[left], nums[i] = nums[i], nums[left]
                left += 1
                i += 1
            elif nums[i] == 2:
                nums[i], nums[right] = nums[right], nums[i]
                right -= 1
                continue
            else:
                i += 1
        print(nums)