75. Sort Colors

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 colors red, white, and blue, respectively.

You must solve this problem without using the library's sort function. (link)

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]

Solution

Brute force Approach

Count the number of 0's, 1's and 2's using 3 variables. Now refill the array using the counts one by one.

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

        for(int i=0; i<nums.length; i++){
            if(nums[i]==0) count0+=1;
            else if(nums[i]==1) count1+=1;
            else count2+=1;
        }

        int index = 0;
        for(int i=0; i<count0; i++){
            nums[index] = 0;
            index+=1;
        }

        for(int i=0; i<count1; i++){
            nums[index] = 1;
            index+=1;
        }


        for(int i=0; i<count2; i++){
            nums[index] = 2;
            index+=1;
        }
    }
}

Dutch National Flag Algorithm

Consider three pointers. Based on these pointers, there are four segments that require attention.

Segment 1: [0, low-1] - Consists of all 0's.

Segment 2: [low, mid-1] - Comprises all 1's.

Segment 3: [mid, high] - Represents the unsorted section.

Segment 4: [high+1, nums.length-1] - Comprises all 2's.

The primary focus is on sorting the third segment. The process starts from the midpoint and continues until it surpasses the high point.

If a 0 is encountered, swap the elements at low and the current mid positions, then increment both low and the current mid.

If a 1 is encountered, no swaps are needed; simply increment mid.

If a 2 is encountered, swap the elements at high and the current mid positions, then increment mid and decrement high.

The underlying concept is to position low/high at an index where the value can be swapped with mid without disrupting the sequence. In the given scenario, swapping 1 and 0 ensures that the 0's segment is correctly ordered, and the 1's segment remains in the correct order as well.

Code

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

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

    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}