Sort Colors

Sorting algorithms play a crucial role in programming. While there are several well-known sorting algorithms available, sorting an array that contains only three distinct elements poses an interesting challenge. The Dutch National Flag problem, named after the Dutch flag with its three colors, presents an intriguing scenario where an array consisting of 0s, 1s, and 2s needs to be sorted in linear time without using additional space.

In this article, we delve into the Dutch National Flag problem and explore an efficient solution to sort such an array. We will discuss the problem’s background, outline the approach used to tackle it and provide a step-by-step explanation of the algorithm. Additionally, we will analyze its time and space complexity to understand its efficiency.

Problem Statement:

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.

---

Approach 1: Counting Sort

So the idea is to iterate through the array and count the number of 0s, 1s, and 2s. Then, overwrite the original array with the counts of each number in the correct order.

1. First, we iterate through the input array and count the occurrences of each number (0, 1 & 2).

2. After counting the occurrences, we iterate through the input array again. For each element, we check its value and use the count information to determine its correct position in the sorted array.

3. Once we have iterated through the entire input array, we have successfully overwritten the original array with the sorted elements in the correct order.

// ES6 Arrow Function
const sortColors = nums => {
    // count of 0s, 1s and 2s
    let count = [0, 0, 0];

    // count the occurrence of each number
    for(let num of nums) count[num]++;

    let index = 0;
    for(let i = 0; i < count.length; i++) {
        while(count[i] > 0) {
            nums[index] = i;
            count[i]--;
            index++;
        }
    }
}

Time Complexity: O(N)

We iterate the array twice, once to count the occurrence of each number and then to overwrite the original array with the sorted numbers. Both of these operations take place in linear time.

Space Complexity: O(1)

The space complexity is constant because the additional space used for counting the occurrences of each number is fixed. It does not depend on the size of the input array.

---

Approach 2: One Pass Algorithm

1. We use two pointers, one at the beginning and one at the end of the array.

2. Initialize two more pointers to keep track of the current index being processed and the index where the next 0 should be placed.

3. Iterate through the array, and if you encounter a 0, swap it with the next 0 position pointer and increment both pointers.

4. If you encounter a 2, swap it with the end pointer and decrement the end pointer.

5. Keep moving the current pointer until it reaches the end pointer.

// ES6 Arrow Function
const sortColors = nums => {
    let low = 0, mid = 0, high = nums.length - 1;

    while(mid <= high) {
        if(nums[mid] === 0) {
            swap(nums, low, mid);
            low++;
            mid++;
        } else if(nums[mid] === 2) {
            swap(nums, mid, high);
            high--;
        } else {
            mid++;
        }
    }
}

// Swap Function
const swap = (arr, a, b) => [arr[a], arr[b]] = [arr[b], arr[a]];

Time Complexity: O(N)

We traverse the array only once with two-pointers and perform constant time operations (swapping elements in place). Therefore, the time complexity is linear.

Space Complexity: O(1)

Since we are modifying the input array in place and not using any additional data structures. The Space complexity is constant.

---

Approach 3: Two Pointers

1. Initialize a pointer to 0, let's say i. This pointer represents the boundary between the section of sorted 0s and the section of sorted 1s.

2. Now, iterate through the array using another pointer, let’s call it j. This pointer represents the current element being processed.

3. If the element at input array, arr[j] is 0, it needs to be placed in the section of sorted 0s. To do this, swap the element at arr[i] with the element at arr[j]. Then, increment i to expand the section of sorted 0s.

4. After the first loop ends, i will point to the index where the section of sorted 1s should begin. Initialize another pointer k to i for the second loop.

5. Iterate through the array again.

6. If the element at arr[m] is 1, it needs to be placed in the section of sorted 1s. To do this, swap the element at arr[m] with the element at arr[k]. Then, increment k to expand the section of sorted 1s.

7. Once both loops are complete, the array will be sorted in the desired order: all 0s on the left, followed by all 1s, and finally all 2s.

// ES6 Arrow Function
const sortColors = nums => {
    let i = 0; 
    for(let j = 0; j < nums.length; j++) {
        if(nums[j] === 0) {
            swap(nums, i, j);
            i++;
        }
    }

    let k = i;
    for(let j = 0; j < nums.length; j++) {
        if(nums[j] === 1) {
            swap(nums, j, k);
            k++;
        }
    }
}

// Swap Function
const swap = (arr, a, b) => [arr[a], arr[b]] = [arr[b], arr[a]];

Time Complexity: O(N)

We are doing two passes through the input array, each taking linear time, where n is the length of the array. Therefore overall time complexity is linear.

Space Complexity: O(1)

The space complexity is constant as we are not using any additional data structure that scales with the input size. All operations are performed in place.

---

And there you have it guys! We’ve explored different approaches, optimized our solutions, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 75