75. Sort Colors

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        time O(N) space O(1)
        [0,zero)  = 0 
        [zero,i) = 1
        [two,len-1] = 2,  two = len-1
    
        """
        # step1: edge case 
        size = len(nums)
        if size < 2 :
            return

        # step2 initialize 
        zero = 0
        two = size
        # step3 define swap function
        def swap(nums,i1,i2):
            nums[i1],nums[i2] = nums[i2],nums[i1]
        
        # step4: loop arr, 3 cases, nums[i] in [0,1,2]
        i = 0
        while i < two:
            if nums[i] == 0:
                swap(nums,i,zero)
                i += 1
                zero += 1 
            elif nums[i]==1:
                i += 1 
            else:  # nums[i] == 2 
                two -= 1 
                swap(nums,i,two)