Algo #119 : Dutch National Flag

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 :)