#
# @lc app=leetcode id=75 lang=python3
#
# [75] Sort Colors
#
# https://leetcode.com/problems/sort-colors/description/
#
# algorithms
# Medium (45.37%)
# Likes:    2829
# Dislikes: 206
# Total Accepted:    444.8K
# Total Submissions: 979.8K
# 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
from collections import Counter

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        colors = Counter(nums)
        c = 0
        i = 0
        while len(colors):
            count = colors[c]
            while count:
                nums[i] = c
                count -= 1
                i += 1
            colors.pop(c, None)
            c+=1
        
# @lc code=end

#
# @lc app=leetcode id=75 lang=python3
#
# [75] Sort Colors
#
# https://leetcode.com/problems/sort-colors/description/
#
# algorithms
# Medium (45.37%)
# Likes:    2829
# Dislikes: 206
# Total Accepted:    444.8K
# Total Submissions: 979.8K
# 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
from collections import Counter

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        colors = Counter(nums)
        c = 0
        i = 0
        while len(colors):
            count = colors[c]
            while count:
                nums[i] = c
                count -= 1
                i += 1
            colors.pop(c, None)
            c+=1
        
# @lc code=end

# # @lc app=leetcode id=75 lang=python3 # # [75] Sort Colors # # https://leetcode.com/problems/sort-colors/description/ # # algorithms # Medium (45.37%) # Likes:    2829 # Dislikes: 206 # Total Accepted:    444.8K # Total Submissions: 979.8K # 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 Do not return anything, modify nums in-place instead. # @lc code=end