Sort Colors

Introduction

Given an array with values 0 representing red, 1 representing white, and 2 representing blue.
You need to modify the array so that all array contains 0s at the start,1s at mid, and 2s at the end.

Note - You cannot use the in-built sorting method and don't create any extra space. Modify the array in its place

Prompt

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]

Solutions

We can solve this problem using different approaches. But as mentioned default sorting method is not allowed and we cannot create any new space, so we have to come up with other solutions. I am going to discuss two solutions here i.e Counting Sort Algorithm and DNF (Dutch National Flag Algorithm)

Counting Sort Algorithm

const sortColors = (nums) => {

    let zero = 0, one = 0, two = 0

    // get count of all zero , one and two
    for (let val of nums) {
        if (val === 0) {
            zero++
        }
        else if (val === 1) {
            one++
        }
        else if (val === 2) {
            two++
        }
    }

    let index = 0
    // populate zero in array
    for (let i = 0; i < zero; i++) {
        nums[index] = 0
        index++
    }

    // populate one in array
    for (let i = 0; i < one; i++) {
        nums[index] = 1
        index++

    }

    // populate two in array
    for (let i = 0; i < two; i++) {
        nums[index] = 2
        index++

    }

    return nums // return array

}
const colors = [1, 1, 2, 2, 0, 0]
sortColors(colors)
console.log(colors)  // [ 0, 0, 1, 1, 2, 2 ]

The time complexity of this code is O(n)+O(n), where n is the length of the input array.

Dutch National Flag Algorithm

The DNF (Dutch National Flag) algorithm is an algorithm for sorting an array of 0's, 1's, and 2's in linear time O(n). The algorithm is named after the flag of the Netherlands, which has three colors: red, white, and blue.

// function for swapping values of array
function swap(arr, low, high) {
    return [arr[low], arr[high]] = [arr[high], arr[low]]
}

const sortColors = (nums) => {

    let low = 0, mid = 0, high = nums.length - 1

    while (mid <= high) {

        let curr = nums[mid]

        if (curr === 0) {
            swap(nums, low, mid)
            low++
            mid++
        } else if (curr === 1) {
            mid++
        } else if (curr === 2) {
            swap(nums, mid, high)

            high--
        }

    }

    return nums
}
const colors = [1, 1, 2, 2, 0, 0]
sortColors(colors)
console.log(colors) // [ 0, 0, 1, 1, 2, 2 ]

The time complexity of this code will be O(n).

Ending note

This problem is a medium-type problem in LeetCode. There could be other solutions available for the same problem.