## DEV Community 👩‍💻👨‍💻 # 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.

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--;
}
}
}
}
`````` 