[LeetCode] 75. Sort Colors

Problem : https://leetcode.com/problems/sort-colors/

Counting sort based solution.

Time Complexity : O ( 2N )

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        colors = [0] * 3
        
        for i in nums:
            colors[i] += 1
        
        j = 0
        for color, count in enumerate(colors):
            for i in range(count):
                nums[j + i] = color
                
            j += count

Two pointers based solution.

Have 'red' pointer moves forward from the first number and 'blue' pointer moves backward from the last number. Iterate from the first number.  If number[i] == 0, swap with red. When number[i] == 2, swap with blue.

Time Complexity : O ( N )

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        def swap(i, j):
            nums[i], nums[j] = nums[j], nums[i]
        
        red, blue = 0, len(nums) - 1
        i = 0
        
        while i <= blue:
            color = nums[i]
            if color == 0:
                swap(i, red)
                red += 1
                i += 1
            elif color == 2:
                swap(i, blue)
                blue -= 1
                # do not increase i
                # need to check the swapped color is red or not
            else:
            	# no need to swap for white color
                i += 1