Step-by-Step Guide to Counting Sort: Solving the Sort Colors Problem

Sort Colors (LeetCode Problem #75). The challenge requires us to sort an array of integers representing the colors red, white, and blue. Red is represented by 0, white by 1, and blue by 2.

Problem Statement

We are given an array nums where each element represents one of three colors: 0 for red, 1 for white, and 2 for blue. The task is to sort the array in-place so that all colors are grouped together in the order: red, white, and blue. We must solve this problem without using any 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]

function sortColors(nums: number[]): void {
    const count: number[] = [0, 0, 0];    
    for (let i = 0; i < nums.length; i++) {
        count[nums[i]]++; 
    }
    let i = 0; // index for nums array  
    for (let color = 0; color < count.length; color++) { 
        for (let j = 0; j < count[color]; j++) { 
            nums[i] = color; 
            i++; 
        }
    }
};

Explanation

• Step 1: We initialize an array count of size 3 to hold the count of each color.

• Step 2: We iterate through the nums array and increment the respective color counts in the count array.

• Step 3: After counting, we iterate through the count array. For each color, we fill nums with the corresponding number of occurrences of that color.

Time and Space Complexity

• Time Complexity:
  The time complexity of this algorithm is O(n), where n is the number of elements in the array.

  • The first loop runs through the nums array to count the occurrences of each color, which takes O(n).

  • The second loop runs through the count array to overwrite nums, which also takes O(n).

Thus, the overall time complexity is O(n + n) = O(n).

• Space Complexity:
  The space complexity is O(1) (constant space) because we are only using a fixed-size array count of length 3, regardless of the input size.

Why Is This Algorithm Unstable?

An algorithm is considered unstable if it does not preserve the relative order of equal elements.

In our solution, nums contains multiple instances of 0, 1, and 2, and after sorting, their original relative order is not guaranteed to be preserved. For example, if the original array is [2, 0, 1], the result will be [0, 1, 2]. While this is correct in terms of sorting, the relative positions of the original 1 and 2 are not preserved, making the algorithm unstable.

Comment if I have committed any mistake. Let's connect on my socials. I am always open for new opportunities , if I am free :P

Linkedin| Twitter | ShowwCase