75. 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.

Approach 01:

#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    void sortColors(vector<int>& nums) {
        unordered_map<int, int> data;
        
        for (int num : nums) {
            data[num]++;
        }
        
        int red = data[0];
        int white = data[1];
        int blue = data[2];
        
        nums.clear();
        
        nums.insert(nums.end(), red, 0);
        nums.insert(nums.end(), white, 1);
        nums.insert(nums.end(), blue, 2);
    }
};

from typing import *

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        data = Counter(nums)

        red = data[0]
        white = data[1]
        blue = data[2]

        nums.clear()
        nums.extend([0]*red)
        nums.extend([1]*white)
        nums.extend([2]*blue)

Time Complexity

• The time complexity of the sortColors function is \( O(n) \), where \( n \) is the number of elements in the input vector nums.
• The function iterates through the vector nums once to count the occurrences of each color, which takes \( O(n) \) time.
• After that, the function clears the vector and inserts the colors back into it based on the counts. Inserting the colors also takes \( O(n) \) time.
• Overall, the total time complexity is \( O(n) + O(n) = O(n) \).

Space Complexity

• The space complexity of the sortColors function is \( O(1) \).
• The unordered_map data used to store the counts of each color has a constant space complexity of \( O(3) \), since there are only three different colors (0, 1, 2).
• The function does not use any additional space that depends on the input size.
• Thus, the overall space complexity is \( O(1) \).

Approach 02:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    void sortColors(vector<int>& nums) {
        map<int, int> mp;
        int i = 0;
        int n = nums.size();

        for(int &n: nums){
          ++mp[n];
        }

        for(auto &it: mp){
            for(int j=0; j<it.second; j++){
              nums[i] = it.first;
              i++;
            }
        }
    }
};

from typing import List
from collections import defaultdict

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        mp = defaultdict(int)
        
        for num in nums:
            mp[num] += 1
        
        i = 0
        for key in sorted(mp.keys()):
            for _ in range(mp[key]):
                nums[i] = key
                i += 1

Time Complexity

• The time complexity of the sortColors function is \( O(n \log k) \), where \( n \) is the number of elements in the input vector nums and \( k \) is the number of distinct keys in the map (which in this case is at most 3 because there are only three different colors: 0, 1, and 2).
• Inserting \( n \) elements into the map takes \( O(n \log k) \) time. Since \( k \) is constant (at most 3), this simplifies to \( O(n) \).
• Iterating over the map and inserting elements back into the vector takes \( O(n) \) time.
• Overall, the total time complexity is \( O(n) + O(n) = O(n) \).

Space Complexity

• The space complexity of the sortColors function is \( O(k) \), where \( k \) is the number of distinct keys in the map.
• The map mp stores the count of each color, and since there are at most 3 distinct colors, the space complexity for the map is \( O(3) \).
• Thus, the overall space complexity is \( O(1) \) because \( k \) is constant (3 distinct colors).