2. Sort Colors

solution

Approach 1: Using Sorting

Sorting is definitely a possible and simple solution to the problem but it surely ain't the most optimal solution for it.

TIME COMPLEXITY : O(NlogN)

SPACE COMPLEXITY : O(1)

Approach 2: Counting Frequency

METHOD 1

Initialization:

• Start by setting up counters for red (0), white (1), and blue (2).
• These counters track the occurrences of each color in the array.

Color Counting Loop:

• Traverse the array, examining each element's color.
• Increment the respective counters for red, white, and blue based on the element's value.

Color Placement :

• Introduce an index (i) to gracefully rearrange the colors.
• Conduct a parade for each color, starting with reds (0), then whites (1), and concluding with blues (2).
• Use counters (count0, count1, count2) to determine the placement.

TIME COMPLEXITY : O(N)+O(N) = O(2N)

SPACE COMPLEXITY: O(1)

import java.io.*;
import java.util.*;
class SortColors_CountFrequency_I
{
    public static void main(String args[]){
        int nums[] = {2,0,2,1,1,0};
        sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void sortColors(int[] nums) {
        int count0 = 0, count1 = 0, count2 = 0;

        for (int ele : nums) {
            if (ele == 0) {
                count0++;
            } else if (ele == 1) {
                count1++;
            } else {
                count2++;
            }
        }

        int i = 0;
        while (count0-- > 0) nums[i++] = 0;
        while (count1-- > 0) nums[i++] = 1;
        while (count2-- > 0) nums[i++] = 2;
    }
}

METHOD 2 ( a better way of doing it ! )

Color Counter Setup:

• Create an array named count with three elements, initialized to zero. This array will serve as our color counter.

Counting Colors:

• Traverse the given array of colors (nums).
• For each color encountered, increment its corresponding count in the count array.

Index Initialization:

• Begin with an index variable i set to 0. This index will navigate through the array, orchestrating the arrangement of colors.

Color Arrangement Loop:

• Iterate through the three colors (0, 1, 2) using a nested loop.
• For each color, engage in the following until its count reaches zero:
• Set the current color at index i in the nums array.
• Increment the index i.
• Decrement the count for the current color.

TIME COMPLEXITY : O(N)+O(N) = O(2N)

SPACE COMPLEXITY: O(1)

import java.io.*;
import java.util.*;
class SortColors_CountFrequency
{
    public static void main(String args[]){
        int nums[] = {2,0,2,1,1,0};
        sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void sortColors(int[] nums) {
        int[] count = new int[3];
        for (int ele : nums) 
            count[ele]++;
        int i = 0;
        for (int color = 0; color <= 2; color++)
        { while (count[color]-- > 0) 
                nums[i++] = color;}
    }
}

Approach 3: Dutch National Flag Algorithm

Three-Pointer Approach:

• low pointer: Points to the position where the next 0 should be placed.
• mid pointer: Traverses through the array.
• high pointer: Points to the position where the next 2 should be placed.

Sorting Logic:

• The goal is to move all 0s to the beginning and all 2s to the end, leaving 1s in the middle.
• The mid pointer helps iterate through the array while the low and high pointers guide the placement of 0s and 2s.

Algorithm Steps:

• When encountering a 0 at mid, swap it with the element at low and increment both pointers (low and mid).
• When encountering a 1 at mid, simply increment mid as 1s should naturally fall in the middle.
• When encountering a 2 at mid, swap it with the element at high and decrement high.
• Repeat these steps until mid surpasses or meets high.

TIME COMPLEXITY : O(N)

SPACE COMPLEXITY: O(1)

import java.io.*;
import java.util.*;
class SortColors_DutchNationalFlag
{
    public static void main(String args[]){
        int nums[] = {2,0,2,1,1,0};
        sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }

    public static void swap(int[] nums, int pos1, int pos2) {
        int temp = nums[pos1];
        nums[pos1] = nums[pos2];
        nums[pos2] = temp;
    }

    public static void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;

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