Sort Colors Solutions in Python

# Source : https://leetcode.com/problems/sort-colors/
# Author : penpenps
# Time   : 2019-05-31

from typing import List

# Counting and reset nums in order
# Time Complexity: O(2*n)
# Space Complexity: O(3)

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        m = [0]*3
        for x in nums:
            m[x] += 1
            
        for i in range(len(nums)):
            if i < m[0]:
                nums[i] = 0
            if m[0] <= i < m[1] + m[0]:
                nums[i] = 1
            if i >= m[0] + m[1]:
                nums[i] = 2
        

if __name__ == '__main__':
	s = Solution()
	nums = [2,0,2,1,1,0]
	s.sortColors(nums)
	print(nums)

# Source : https://leetcode.com/problems/sort-colors/
# Author : penpenps
# Time   : 2019-05-31

from typing import List

# Quick sort for 3 numbers
# Time Complexity: O(n)
# Space Complexity: O(3)

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

if __name__ == '__main__':
	s = Solution()
	nums = [2,0,2,1,1,0]
	s.sortColors(nums)
	print(nums)

# Source : https://leetcode.com/problems/sort-colors/
# Author : penpenps
# Time   : 2019-05-31

from typing import List

# use [i, j) to keep 0, [j, k) keeps 1 and [k, ] keeps 2
# Time Complexity: O(n)
# Space Complexity: O(4)

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i, j, k = 0, 0, 0
        for k in range(len(nums)):
            v = nums[k]
            nums[k] = 2
            if v < 2:
                nums[j] = 1
                j += 1
            if v < 1:
                nums[i] = 0
                i += 1
        

if __name__ == '__main__':
	s = Solution()
	nums = [2,0,2,1,1,0]
	s.sortColors(nums)
	print(nums)