Sort three colors in an array

Given an array containing three different colors red ,white and blue denoted by numbers 0,1 and 2 sort the array such that red comes first followed by white followed by blue.

Constraints:

• Do not use any extra space (solve it in place)
• Time complexity should be O(n) where n is the number of elements.

For example,

Given the input:

[2,0,1,0,2,1]

The output is

[0,0,1,1,2,2]

Try out the solution here:

https://leetcode.com/problems/sort-colors/

Solution:

Approach 1 – Count the number of 0s,1s and 2s

In this approach you scan the array once and count the number of zeroes, ones and twos.

Once you know that you can fill in the array with zeroes first then ones and finally twos.

Here is the algorithm:

class Solution {
    public void sortColors(int[] nums) {
        
        
        int zero = 0;
        int one = 0;
        int two = 0;
        
        
        for(int i:nums){
            
            if(i == 0) zero++;
            if(i == 1) one++;
            if(i == 2) two++;
        }
        int index = 0;
        for(int i = 0;i<zero;i++){
            
            nums[index++] = 0;
        }
             for(int i =0;i<one;i++){
            
            nums[index++] = 1;
        }
             for(int i =0;i<two;i++){
            
            nums[index++] = 2;
        }
        
        
        
        
    }
}

Time complexity is O(2n) = O(n) and space complexity is O(1)

We do two scans here .

We need to do it in a single scan.

Approach 2 – Dutch National Flag problem

This problem is also called Dutch National Flag problem and Edsger W. Dijkstra has proposed the below algorithm to solve it:

• Have three pointers :
• one to indicate the right most boundary of 0s (left pointer),
• another to indicate the right most boundary of 1s (middle pointer) and
• the last to indicate the left most boundary of 2s (right pointer)
• Initialize left and middle pointers to zero and right pointer to the last element

• While the middle pointer is less than or equal to the right pointer do the following:
  • If the element pointed to by the middle pointer is equal to zero :
    • Swap the elements pointed by the left and middle pointer and
    • increment left and middle pointer
  • If the element pointed to by the middle pointer is equal to two:
    • Swap the elements pointed by the middle and right pointer and
    • decrement right pointer
  • If the element pointed to by the middle pointer is equal to zero :
    • Increment middle pointer (no swapping)

Here is the code:

class Solution {
    public void sortColors(int[] nums) {
        
        
        int left = 0;
        
        int right = nums.length - 1;
        
        int middle = 0;
        
        
        while(middle <= right){
            
            
            if(nums[middle] == 0){
                
                
                int temp = nums[left];
                nums[left] = nums[middle];
                nums[middle] = temp;
                
                left++;
                middle++;
                
            }else if(nums[middle] == 2){
                
                
                
                int temp = nums[middle];
                nums[middle] = nums[right];
                nums[right] = temp;
                
                right--;
                
            }else{
                middle++;
            }
        }
        
    }
}

Time complexity is O(n) and space complexity is O(1).

Also we make only a single pass.

That’s it!