Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Dutch National Flag Problem

Sort an array of balls having colors R, W and B such that all balls with the same color are contiguous (i.e. form one group for each color).

Solution: Let us do it for two colors first.
```int lo = 1;
int hi = arr.length-1;

while (lo < hi)
{
if (arr[lo] == 0)
{
lo++;
}
else
{
swap (arr, lo, hi);
hi--;
}
}
```

For 3 colors, we will maintain 4 regions, demarcated by 3 positions (Lo, Mid and Hi):
1. a[1..Lo-1] zeroes (red)

2. a[Lo..Mid-1] ones (white)

3. a[Mid..Hi] unknown

4. a[Hi+1..N] twos (blue)

The unknown region is shrunk while maintaining these conditions by the following code:
```int lo  = 1;
int mid = 1;
int hi  = arr.length-1;

while (mid < hi)
{
if (arr[mid] == 0)
{
swap (arr, lo, mid);
lo++;
mid++;
}
else if (arr[mid] == 1)
{
mid++;
}
else if (arr[mid] == 2)
{
swap (arr, mid, hi);
hi--;
}
}
```

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: