75. Sort Colors

Description:

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.

'''
[1] using library function)

-T/C: O(nlogn)
-S/C: O(1)
'''

'''
[2] using hashmap)

idea::
1. count all values, like 0: 3, 1: 2, 2: 4
2. then, overwrite it

code::

counter={0:0, 1:0, 2:0}
for num in nums:
    counter[num]+=1
    
for i in range(len(nums)):
    if counter[0]>0:
        nums[i]=0
        counter[0]-=1
    elif counter[1]>0:
        nums[i]=1
        counter[1]-=1
    else:
        nums[i]=2

-T/C: O(n) # two pass
-S/C: O(n) # for hashmap
'''


'''
[3] three-pointer)

idea::
pointers : 0-writer, 2-writer, reader
while traversal from 0 to len(nums)-1, if num[i]==0, then move to left side, elif num[i]==2, then move to right side

code::
    def sortColors(self, nums: List[int]) -> None:
        reader=0
        left_writer=0
        right_writer=len(nums)-1
        
        while reader<=right_writer:
            if nums[reader]==0:
                nums[reader],nums[left_writer]=nums[left_writer],nums[reader]
                left_writer+=1
                reader+=1
            elif nums[reader]==2:
                nums[reader],nums[right_writer]=nums[right_writer],nums[reader]
                right_writer-=1
            else:
                reader+=1
-T/C: O(n)
-S/C: O(1)
'''

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        reader=0
        left_writer=0
        right_writer=len(nums)-1
        
        while reader<=right_writer:
            if nums[reader]==0:
                nums[reader],nums[left_writer]=nums[left_writer],nums[reader]
                left_writer+=1
                reader+=1
            elif nums[reader]==2:
                nums[reader],nums[right_writer]=nums[right_writer],nums[reader]
                right_writer-=1
            else:
                reader+=1