#
# @lc app=leetcode id=75 lang=python3
#
# [75] Sort Colors
#
# https://leetcode.com/problems/sort-colors/description/
#
# algorithms
# Medium (45.00%)
# Likes:    3402
# Dislikes: 226
# Total Accepted:    511.5K
# Total Submissions: 1.1M
# Testcase Example:  '[2,0,2,1,1,0]'
#
# Given an array 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.
# 
# Here, we will use the integers 0, 1, and 2 to represent the color red, white,
# and blue respectively.
# 
# Note: You are not suppose to use the library's sort function for this
# problem.
# 
# Example:
# 
# 
# Input: [2,0,2,1,1,0]
# Output: [0,0,1,1,2,2]
# 
# Follow up:
# 
# 
# A rather straight forward solution is a two-pass algorithm using counting
# sort.
# First, iterate the array counting number of 0's, 1's, and 2's, then overwrite
# array with total number of 0's, then 1's and followed by 2's.
# Could you come up with a one-pass algorithm using only constant space?
# 
# 
#

# @lc code=start
class Solution:
    def sortColors(self, nums: list) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        ret = []
        numslen = len(nums)

        zero = 0
        two = numslen - 1

        idx = 0

        if numslen == 0:
            return ret
        
        while idx < numslen:
            if nums[idx] == 0:
                nums[idx], nums[zero] = nums[zero], nums[idx]
                zero += 1
                idx += 1
            elif nums[idx] == 2:
                if idx > two:
                    break
                nums[two], nums[idx] = nums[idx], nums[two]
                two -= 1
            else:
                idx += 1
        ret = nums        
        return ret

if __name__ == "__main__":
    solu = Solution()
    nums = [2,2,2,2,2]
    ret = solu.sortColors(nums)
    print(ret)
        
# @lc code=end

