Leetcode 75. Sort Colors
---
###### tags: `Leetcode`
---

[link](https://leetcode.com/problems/sort-colors/)

---

Given an array nums 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.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

#### Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

#### Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

#### Constraints:

- n == nums.length
- 1 <= n <= 300
- nums[i] is either 0, 1, or 2.
---

It initializes counts as a list of three zeros, representing the counts of 0s, 1s, and 2s in the nums list.

It iterates over the nums list and increments the respective count in counts for each element. It then uses nested loops to iterate over the counts in counts and modifies the nums list in-place. The outer loop iterates over the range of counts (0, 1, and 2).

The inner loop iterates counts[j] times, which represents the count of the current element. Inside the inner loop, it sets the value of nums[n] to the current element represented by j, where n is the current index in the nums list. It then increments n by 1.

Essentially, this step replaces the elements in nums with the sorted order of 0s, 1s, and 2s, using the counts stored in counts.

#### Solution 1

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        counts = [0, 0, 0]
        for i in nums:
            counts[i] += 1

        n = 0
        for j in range(len(counts)):
            for k in range(counts[j]):
                nums[n] = j
                n += 1
        

O(T): O(n)
O(S): O(1)