In this post we will solve the LeetCode 75. Sort Colors problem using the Java programming language and the VSCode IDE on a Windows computer.
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. Constraints: o n == nums.length o 1 <= n <= 300 o nums[i] is 0, 1, or 2.
We are given an integer array with values 0, 1, and 2 which represent colors red, white and blue respectively. We must solve the problem without the use of any library sort function. That makes sense because we would only have to sort the input array and return.
If you are interested in this problem I would suggest for you to first look at the current problem definition in the LeetCode website. Some aspects of the problem may change with time.
public void sortColors(int[] nums) {
}
The signature for the function of interest is simple. We are given the array with the three colors and we need to sort them in place before returning to the caller.
I like to develop software using the Test Driven Development () approach. That means that as the function of interest is being developed, I make sure that things are working. Not using such an approach implies that after the first pass of the code is completed, testing starts.
Because of TDD I develop the code on my own computer. Such an approach requires a simple test scaffold so we can test as the code progresses. Please note that the test code IS NOT PART OF THE SOLUTION.
2,0,2,1,1,0 main <<< nums: [2, 0, 2, 1, 1, 0] <<< c0: 2 c1: 2 c2: 2 <<< nums: [0, 0, 1, 1, 0, 0] main <<< output: [0, 0, 1, 1, 2, 2] 2,0,1 main <<< nums: [2, 0, 1] <<< c0: 1 c1: 1 c2: 1 <<< nums: [0, 1, 0] main <<< output: [0, 1, 2] 0 main <<< nums: [0] main <<< output: [0] 1 main <<< nums: [1] main <<< output: [1] 2,0,2,0,0,2 main <<< nums: [2, 0, 2, 0, 0, 2] <<< c0: 3 c1: 0 c2: 3 <<< nums: [0, 0, 0, 0, 0, 0] <<< nums: [0, 0, 0, 2, 2, 2] main <<< output: [0, 0, 0, 2, 2, 2] 1,2,2,1,1,2,1 main <<< nums: [1, 2, 2, 1, 1, 2, 1] <<< c0: 0 c1: 4 c2: 3 <<< nums: [1, 1, 1, 1, 0, 0, 0] <<< nums: [1, 1, 1, 1, 2, 2, 2] main <<< output: [1, 1, 1, 1, 2, 2, 2] 0,1,2,2,1,0,1,0,2,2 main <<< nums: [0, 1, 2, 2, 1, 0, 1, 0, 2, 2] <<< c0: 3 c1: 3 c2: 4 <<< nums: [0, 0, 0, 1, 1, 1, 0, 0, 0, 0] <<< nums: [0, 0, 0, 1, 1, 1, 2, 2, 2, 2] main <<< output: [0, 0, 0, 1, 1, 1, 2, 2, 2, 2] 1,0,1,0,1,1,0 main <<< nums: [1, 0, 1, 0, 1, 1, 0] <<< c0: 3 c1: 4 c2: 0 <<< nums: [0, 0, 0, 1, 1, 1, 1] main <<< output: [0, 0, 0, 1, 1, 1, 1]
Each test case is separated by two blank lines.
The first line represents input for the contents of the `nums` int[] array. Our test code seems to read the input line, allocate an int[], populate it and then display it for us to verify that all is well so far (yes, I am using a TDD approach).
I implemented two solutions. The output corresponds to the second implementation. As we will see shortly, we can switch from one implementation to the other by just changing a single character in the code (the name of the function of interest).
At some point the function of interest returns to the caller (the test code) and the contents of the `nums` array is displayed. Not sure if all colors are always present in the input arrays. The two implementations do not seem to care about missing colors.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read int[] nums ****
int[] nums = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nums: " + Arrays.toString(nums));
// **** call function of interest ****
sortColors(nums);
// **** display int[] nums array ****
System.out.println("main <<< output: " + Arrays.toString(nums));
}
Our test code used a buffered reader to read the contents of the input line returning the int[] nums. The continents of the input array are displayed to allow us to verify that all is well before calling the function of interest. The function of interest is called. The contents of the `nums` int[] are displayed. It should be ordered in ascending color values.
/**
* 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.
*
* 87 / 87 test cases passed.
* Status: Accepted
* Runtime: 2 ms
* Memory Usage: 37.5 MB
*
* Execution: O(n) - Space: O(n)
*/
static public void sortColors0(int[] nums) {
// **** sanity checks ****
if (nums.length == 1) return;
// **** initialization ****
PriorityQueue<Integer> pq = new PriorityQueue<>();
// **** insert int[] nums contents into the priority queue - O(n) ****
for (int n : nums) pq.add(n);
// **** copy contents from pq into nums - O(n) ****
for (int i = 0; !pq.isEmpty(); i++)
nums[i] = pq.remove();
}
My first thought was to use a priority queue. We add all the values from the `nums` int[] array. We then enter a loop in which we remove all the values from the priority queue and place them in the `nums` array. The contents of the array should now be sorted.
This solution was accepted. Not bad but perhaps we could do better! Please take a look at the comments section associated with this function in the code to get runtime statistics.
/**
* 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.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 37.3 MB, less than 98.13% of Java online submissions.
*
* 87 / 87 test cases passed.
* Status: Accepted
* Runtime: 0 ms
* Memory Usage: 37.3 MB
*
* Runtime: O(n) - Space: O(1)
*/
static public void sortColors(int[] nums) {
// **** sanity checks ****
if (nums.length == 1) return;
// **** initialization ****
int len = nums.length;
int c0 = 0;
int c1 = 0;
int c2 = 0;
// **** count colors - O(n) ****
for (int i = 0; i < len; i++) {
if (nums[i] == 0) c0++;
else if (nums[i] == 1) c1++;
else c2++;
}
// ???? ????
System.out.println("<<< c0: " + c0 + " c1: " + c1 + " c2: " + c2);
// **** clear nums (all entries are red) ****
Arrays.fill(nums, 0);
// **** restore white ***
if (c1 != 0) Arrays.fill(nums, c0, c0 + c1, 1);
// ???? ????
System.out.println("<<< nums: " + Arrays.toString(nums));
// **** restore blue ****
if (c2 != 0) Arrays.fill(nums, c0 + c1, len, 2);
}
It seems that we should remove the priority queue from the next implementation. As you can see we did. The idea is to count the different colors. Once that is done, we can fill in the `nums` array the colors using the different counts.
The initial loop performs the counts of the three colors.
We then fill the entire array with red. We follow by filling the next color (white) and finally the blue color. As you can see, missing colors are acceptable.
At this point we are done. There is no need to return a value since the result is in the `nums` array that was passed by reference.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named SortColors.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., Codility_, HackerRank, LeetCode to name a few).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John