Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place 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.

Note: You are not suppose to use the library's sort function for this problem.

Example:

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

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

        while (mid <= high) {
            switch (nums[mid]) {
                case 0: {
                    temp = nums[low];
                    nums[low] = nums[mid];
                    nums[mid] = temp;
                    low++;
                    mid++;
                    break;
                }
                case 1:
                    mid++;
                    break;
                case 2: {
                    temp = nums[mid];
                    nums[mid] = nums[high];
                    nums[high] = temp;
                    high--;
                    break;
                }

            }
        }
    }

}

Try it on Leetcode

Logic behind this algorithm - Dutch National Flag Problem

Here we are mainly using three variables -low, mid, high.

1) Keep three indices low = 0, mid = 0 and high = nums.length-1.

2) If the element is 0 then swap the element with the element at index low and update low = low + 1 and mid = mid + 1

3) If the element is 1 then update mid = mid + 1

4) If the element is 2 then swap the element with the element at index high and update high = high – 1 . As the swapped element is not processed

Finally the array is sorted.

Related Posts:

Click here for May month challenges with solution and explanation
Click here for April month challenges with solution and explanation

Click here for June Month challenges with solution and explanation

Subscribe us to receive updates instantly.

Please let us know about your views in comment section.

Happy Coding...😍