Dutch National Flag Algorithm (or) 3 Way Array Partitions[Leetcode Sort Colors]

Dsa - Arrays

Hey devs hope you all are doing well!

Today we are going to learn an array based algorithm called dutch flag algorithm A.K.A 3 way parition algorithm.

Before going through this article make sure you are good with array basics.

Arrays basics : https://www.cs.fsu.edu/~myers/c++/notes/arrays.html#:~:text=An%20array%20is%20an%20indexed,therefore%2C%20the%20same%20size).

Where is the Algorithm used ?

The idea behind the algorithm is to partition an array into 3 parts using 3 pointers and can be used to sort arrays having 3 values (which can be repeated any no. of times) Ex: [0,2,1,2,0,2,2].(Sort array with 0s,1s and 2s).

Procedure :

1. Take an unsorted array with 0s,1s and 2s.(Or any 3 numbers).

2. Initialize 3 variables low , mid , high with the below values :

• low : 0
• mid : 0
• high: n-1 (Where n is the no. of array entries).

3.When the algorithm is completed elements from :

• index 0 -> low will have 0s.
• index low -> mid will have 1s.
• index mid -> high will have (0s/1s/2s).
• index high -> n will have 2s.

4.There are 3 cases in this algorithm as mid moves along the array until it crosses high.

5.IF list[mid] == 0 (list is our array)

• Swap the values of list[mid] and list[low].
• Increment low and mid by one unit.
• We do this to ensure all 0s are put to the front.

6.IF list[mid] == 1

• No swap is needed
• Increment only mid by one unit.

7.IF list[mid] == 2

• Swap list[mid] and list[high]
• Increment mid and decrement high.
• We do this to ensure all 2s are put to the end.

8.When mid crosses high the algorithm ends and we get a sorted array.

Time Complexity : O(n)

Space Complexity : O(1)

Try out yourself

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

Source Code

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

            if(value == 0)
            {
                    int swapvalue = nums[mid];
                    nums[mid] = nums[low];
                    nums[low] = swapvalue;
                    mid++;
                    low++;
            }
            else if(value == 1)
                mid++;             
            else if(value == 2)
            {
                int swap = nums[mid];
                nums[mid] = nums[high];
                nums[high] = swap;
                    high--;
            }
    }
}
}