Arrays - Sort Colors

Given an array nums 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.

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

You must solve this problem without using the library's sort function

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

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

Follow up:

Could you come up with a one-pass algorithm using only constant extra space?

Solution 1 - Count 0's, 1's and 2's, then places them in order
Solution 2 - Using two pointers, move all 0's to left and 2's to the right side (answer to the follow-up question)

In this approach, we will first count number of 0's, 1's and 2's in the input array nums and then place them in the order back into the input array.

import java.util.Arrays; public class SortColors { static int[] countOccurrencesAndAddThemToResult(int[] nums) { // first count 0's, 1's and 2's, below we are counting just zeros and ones, // any remaining are twos int zeros = 0; int ones = 0; for (int num : nums) { if (num == 0) { zeros++; } else if (num == 1) { ones++; } } // once we know how many 0's, 1's and 2's are there, place them back into the array. for (int i = 0; i < nums.length; i++) { if (i < zeros) { nums[i] = 0; } else if (i < zeros+ones) { nums[i] = 1; } else { nums[i] = 2; } } return nums; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input array nums length.
Space complexity: O(1)

In this approach, we will use two pointers to indicate left and right ends of the array and another pointer to indicate the current position of array that will go through from left to right. Then move all 0's to the left side, 2's to the right side and bring 1's to the middle.

implementation details:

We will first initialize two variables left = 0 to start from left end of the array and right = nums.length -1 to start from right end of array. Also initialize another variable current =0 that we will use to traverse through array.
Then we will start looping through input array until current reaches right, that means when these two intersect all 0's will be on left side and 2's will be on right side.
1. If the element at current index is 0, then swap elements at current index with left (by doing so, we have made sure that 0 elements are moved to left side), now increment both current and left indexes.
2. If the element at current index is 1, then simply increment current index as 1 is in the right position.
3. If the element at current index is 2, then swap elements at current index with right (by doing so, we have made sure that 2 elements are moved to right side), now decrement right index.
  The reason we are not updating current index is because, after swapping right indexed element with current the element swappet to current index may be 2 again.

Let's look at an example, say if the given input array is nums = [2,0,2,1,1,0]

We will first create two pointers left = 0 and right = 5, also create current = 0 to iterate through elements.
In the first iteration, current = 0 indexed element is 2, so we swap it with right = 5 index, so the array now becomes [0,0,2,1,1,2], and right will become 4.
In the second iteration, current = 0 indexed element is 0, so we swap it with left = 0 index, and the array now becomes [0,0,2,1,1,2] and current index becomes 1 and left also becomes 1.
In the third iteration, current = 1 indexed element is 0, so we swap it with left = 1 index, and the array now becomes [0,0,2,1,1,2] and current index becomes 2 and left also becomes 2.
In the fourth iteration, current = 2 indexed element is 2, so we swap it with right = 4, and the array now becomes [0,0,1,1,2,2], and right will become 3.
In the fifth iteration, current = 2 indexed element is 1, so we will increment current to 3.
In the sixth iteration, current = 3 indexed element is 1, so we will increment current to 4.
Now current = 4 index is creater than right = 3, so all elements are in order.

import java.util.Arrays; public class SortColors { static int[] usingTwoPointers(int[] nums) { int left= 0; int right = nums.length -1; int current = 0; while(current<=right) { if(nums[current] == 0){ int temp = nums[left]; nums[left] = nums[current]; nums[current] = temp; left++; current++; } else if (nums[current] ==1) { current++; } else { int temp = nums[right]; nums[right] = nums[current]; nums[current] = temp; right--; } } return nums; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input array nums length.
Space complexity: O(1)

Above implementations source code can be found at GitHub link for Java code

Follow up:

Contents

Complexity Analysis:

implementation details:

Complexity Analysis: