75. Sort Colors

Description

The problem is to sort an array of integers that contains only the values 0, 1, and 2. The goal is to arrange the elements such that all the 0s come first, followed by all the 1s, and then all the 2s, in linear time.

Intuition

The task can be solved using a counting approach where we first count the occurrences of each value (0, 1, and 2), and then overwrite the original array using these counts. This method ensures that the array is sorted in a single pass after counting.

Approach

1. Counting Phase: Traverse the array and maintain a count of 0s, 1s, and 2s.
2. Overwriting Phase: Iterate through the array again and overwrite it with the correct number of 0s, followed by 1s, and then 2s based on the counts from the first phase.
3. This approach ensures the sorting is done in linear time, as each element is processed a constant number of times.

Complexity

Time Complexity:

O(n) - where n is the length of the array. We traverse the array twice: once for counting and once for overwriting.

Space Complexity:

O(1) - We only use a fixed amount of extra space for the count array, making this approach very space-efficient.

Code

C++

class Solution {
public:
    void sortColors(vector& nums) {
        int count[3] = {0, 0, 0};
        for (int i = 0; i < nums.size(); i++) {
            count[nums[i]]++;
        }
        int idx = 0;
        for (int color = 0; color < 3; color++) {
            for (int j = 0; j < count[color]; j++) {
                nums[idx] = color;
                idx++;
            }
        }
    }
};

Python

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        count = {0: 0, 1: 0, 2: 0}
        for num in nums:
            count[num] += 1
        idx = 0
        for color in range(3):
            for _ in range(count[color]):
                nums[idx] = color
                idx += 1

Java

class Solution {
    public void sortColors(int[] nums) {
        int[] count = new int[3];

        for (int i = 0; i < nums.length; i++) {
            count[nums[i]]++;
        }
        int idx = 0;
        for (int color = 0; color < 3; color++) {
            for (int j = 0; j < count[color]; j++) {
                nums[idx] = color;
                idx++;
            }
        }
    }
}

JavaScript

var sortColors = function (nums) {
    let count = { 0: 0, 1: 0, 2: 0 };

    for (let i = 0; i < nums.length; i++) {
        count[nums[i]]++;
    }
    let idx = 0;
    for (let color = 0; color < 3; color++) {
        let freq = count[color];
        for (let j = 0; j < freq; j++) {
            nums[idx] = color;
            idx++;
        }
    }
};