**Problem Statement:**

**Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.**

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

OR

Sort a given array consisting of 0s,1s and 2s.

Input : [ 1,2,0,2,0,1,0,2 ]

Output: [ 0,0,0,1,1,2,2,2 ]

**Solution:**

This problem is very known problem and is commonly asked in interviews and is also known as

**Dutch National Flag Algorithm**, another variant of this problem consists of only 0s and 1s.

In this problem we will be taking up 3 pointers, the strategy behind solving this problem is to divide the array into three regions. The mid pointer traverses over the array , if

**'0'**is encountered swap mid and low pointer elements , if '1' is encountered skip, if '2' is encountered swap mid and high pointer elements.

Below is the Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | int[] sort(int[] arr) { if (arr != null) { int len = arr.length; int low = 0; int mid = 0; int high = len - 1; while (mid <= high) { switch (arr[mid]) { case 0: swap(arr, mid++, low++); break; case 1: mid++; break; case 2: swap(arr, mid, high--); break; } } } return arr; } void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } |

Time Complexity : O(n)

Space Complexity: O(1)

Please comment and post suggestions if any.

Happy Coding :)

## No comments:

## Post a Comment