It is Sunday October 31, 2021 and you are correct, it is Halloween. Woke up as usual just before 06:00 AM. The temperature outside was 39F and the inside temperature was 66F. It all started nine days ago when I noticed that the furnace was not generating heat. This morning the second company that my wife and I selected for the job showed up with a brand new furnace. The two technicians in a pickup truck towing a closed trailer set sheets on the floor in the lower level from the door to the utility room.
In less than a couple hours the furnace was removed and loaded in the trailer. When they were hailing in the new furnace, two more technicians showed up to help. It seems that the job will be done in about four hours. I was impressed with the quality of job, courtesy and attention to detail.
If you live in the Twin Cities of Minneapolis and St. Paul area and have an issue with your furnace of AC units, leave me a message and I will pass on the name of the company.
As I am getting ready to publish this post the furnace crew is finishing testing the installation of the furnace and is starting to put the furniture back in place. I was expecting that the job would take about six hours, but due to the additional number of technicians the job should be completed in less than five hours!!!
I continue solving the problems in the Algorithm I section of LeetCode. Today we will tackle the LeetCode 283 Move Zeroes problem using the Java programming language and the VSCode IDE on a Windows platform. Given that Java is quite portable you should be able to develop the code on any platform and with any IDE. Of course, the simplest option is to use the on-line IDE provided by LeetCode.
Given an integer array nums, move all 0's to the end of it `while maintaining the relative order` of the non-zero elements. Note that you must do this in-place without making a copy of the array. Constraints: o 1 <= nums.length <= 104 o -231 <= nums[i] <= 231 - 1 Related Topics: o Arrays o Two Pointers Follow up: Could you minimize the total number of operations done?
The requirements are quite simple. We are given an int[] array with a combination of zero and non-zero values. Our task is to move the non zero values to the front of the array leaving them in the same order. The rest of the array should contain the zero entries.
The note that calls for not using an additional array seems to have been added at some point to the initial requirements. What called my attention was the follow up note that promotes the simplest possible solution. As you will see shortly, I spent time implementing several versions of the function of interest. At the same time, the four technicians were next door to my office in the utility room, talking and making noise while working to get the furnace replaced as fast as possible.
public void moveZeroes(int[] nums) {
}
The signature for the function of interest uses a single argument.
0,1,0,3,12 main <<< nums: [0, 1, 0, 3, 12] <<< nums: [1, 0, 0, 3, 12] <<< nums: [1, 3, 0, 0, 12] <<< nums: [1, 3, 12, 0, 0] main <<< output: [1, 3, 12, 0, 0] 0 main <<< nums: [0] main <<< output: [0] 1,2,3,4,5 main <<< nums: [1, 2, 3, 4, 5] <<< nums: [1, 2, 3, 4, 5] <<< nums: [1, 2, 3, 4, 5] <<< nums: [1, 2, 3, 4, 5] <<< nums: [1, 2, 3, 4, 5] <<< nums: [1, 2, 3, 4, 5] main <<< output: [1, 2, 3, 4, 5] 0,0,0,0,0 main <<< nums: [0, 0, 0, 0, 0] <<< nums: [0, 0, 0, 0, 0] main <<< output: [0, 0, 0, 0, 0] 0,1,0,2,0,3,0 main <<< nums: [0, 1, 0, 2, 0, 3, 0] <<< nums: [1, 0, 0, 2, 0, 3, 0] <<< nums: [1, 2, 0, 0, 0, 3, 0] <<< nums: [1, 2, 3, 0, 0, 0, 0] main <<< output: [1, 2, 3, 0, 0, 0, 0] 0,1,2,0,0,0,3,4,5,0 main <<< nums: [0, 1, 2, 0, 0, 0, 3, 4, 5, 0] <<< nums: [1, 0, 2, 0, 0, 0, 3, 4, 5, 0] <<< nums: [1, 2, 0, 0, 0, 0, 3, 4, 5, 0] <<< nums: [1, 2, 3, 0, 0, 0, 0, 4, 5, 0] <<< nums: [1, 2, 3, 4, 0, 0, 0, 0, 5, 0] <<< nums: [1, 2, 3, 4, 5, 0, 0, 0, 0, 0] main <<< output: [1, 2, 3, 4, 5, 0, 0, 0, 0, 0] 1,0 main <<< nums: [1, 0] <<< nums: [1, 0] main <<< output: [1, 0] 0,1 main <<< nums: [0, 1] <<< nums: [1, 0] main <<< output: [1, 0] 1,0,0 main <<< nums: [1, 0, 0] <<< nums: [1, 0, 0] main <<< output: [1, 0, 0]
The test cases require a single input line. The line holds the integer values for the `nums` array which is the single argument for the function of interest.
Our test scaffold which IS NOT PART OF THE SOLUTION, seems to read the input line and populate the `nums` int[] array. The contents of the `nums` array is then displayed to make sure all is well before calling the function of interest.
As I mentioned earlier we will go over several implementations of the function of interest. Most of them display different values to help us understand the algorithm. All the test cases in this pass are associated with the last implementation. I decided it would take too much space to post the screen captures for all the different implementations.
The last line in each test case displays the modified `nums` array.
Some of the test cases came from LeetCode while others I made up.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read nums int[] ****
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 ****
// moveZeroes0(nums);
// moveZeroes1(nums);
// moveZeroes2(nums);
// moveZeroes3(nums);
moveZeroes(nums);
// **** display output ****
System.out.println("main <<< output: " + Arrays.toString(nums));
}
This is the test scaffold. This code is only needed if you develop the solution on your machine. This code IS NOT PART OF THE SOLUTION.
The test scaffold is quite simple. We just populate the int[] `nums`, display it to make sure all is well before we call the function of interest, call the function of interest and display the update `nums` array. Not much to say about the test code.
/**
* Given an integer array nums, move all 0's to the end of it
* while maintaining the relative order` of the non-zero elements.
*
* 74 / 74 test cases passed.
* Status: Accepted
* Runtime: 32 ms
* Memory Usage: 40 MB
*
* Runtime: O(n) - Space: O(1)
*/
public static void moveZeroes0(int[] nums) {
// **** sanity check(s) ****
// if (nums.length == 1) return;
// **** initialization ****
int z = 0;
int n = 0;
// **** loop until last entry - O(n) ****
while (n <= nums.length || z <= nums.length) {
// **** look for the next zero - O(n) ****
while (z < nums.length && nums[z] != 0) z++;
// **** check if we are out of zeroes ****
if (z >= nums.length) return;
// ???? ????
System.out.println("<<< z: " + z + " nums[" + z + "]: " + nums[z]);
// **** look for the next non-zero - O(n) ****
for (n = z + 1; n < nums.length && nums[n] == 0; ) n++;
// **** check if we are out of non-zeroes ****
if (n >= nums.length) return;
// ???? ????
System.out.println("<<< n: " + n + " nums[" + n + "]: " + nums[n]);
// **** swap zero and non-zero values ****
// int tmp = nums[z];
// nums[z] = nums[n];
// nums[n] = tmp;
swap(nums, z, n);
// ???? ????
System.out.println("<<< n: " + n + " z: " + z + " nums: " + Arrays.toString(nums));
}
}
This function performs a sanity check and initialization.
It then enters a loop which keeps track of the indices of zero and non-zero values. On each pass it swaps the non-zero values in order to move them to the front part of the `nums` array.
To be honest with you, we will use the same idea in all implementations of the function of interest. What will change is the way we update the indices in order to get simpler and more efficient code.
Please keep in mind that the execution times as recorded by LeetCode are included in the comment section of each implementation.
/**
* Given an integer array nums, move all 0's to the end of it
* while maintaining the relative order` of the non-zero elements.
*
* Runtime: O(n) - Space: O(n)
*
* 74 / 74 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 40.6 MB
*/
public static void moveZeroes1(int[] nums) {
// **** initialization ****
int len = nums.length;
int zeroCount = 0;
int[] arr = new int[len];
// **** count zero values ****
for (int i = 0; i < len; i++)
if (nums[i] == 0) zeroCount++;
// ???? ????
System.out.println("<<< zeroCount: " + zeroCount);
// **** copy non-zero values - O(n) ****
for (int i = 0, j = 0; i < len; i++) {
if (nums[i] != 0) {
arr[j++] = nums[i];
}
}
// ???? ????
System.out.println("<<< arr: " + Arrays.toString(arr));
// **** copy values in order - O(n) ****
for (int i = 0; i < len; i++)
nums[i] = arr[i];
}
In this implementation we use an auxiliary array which is not allowed by the current requirements. You can ignore this implementation which was accepted by LeetCode.
/**
* Given an integer array nums, move all 0's to the end of it
* while maintaining the relative order` of the non-zero elements.
*
* Runtime: O(n) - Space: O(1)
*
* 74 / 74 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 40 MB
*/
public static void moveZeroes2(int[] nums) {
// **** initialization ****
int lastNonZeroNdx = 0;
int len = nums.length;
// **** move non-zero values left - O(n) ****
for (int i = 0; i < len; i++) {
if (nums[i] != 0)
nums[lastNonZeroNdx++] = nums[i];
}
// ???? ????
System.out.println("<<< nums: " + Arrays.toString(nums));
// **** set to zero values to right of last non-zero entry - O(n) ****
for (int i = lastNonZeroNdx; i < len; i++)
nums[i] = 0;
}
In this implementation we are first moving the non-zero values to their final position. This is done in the first loop.
In the second loop we set to zero the remaining values towards the right side of the `nums` array.
/**
* Given an integer array nums, move all 0's to the end of it
* while maintaining the relative order` of the non-zero elements.
*
* 74 / 74 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 40.4 MB
*
* Runtime: O(n) - Space: O(1)
*/
public static void moveZeroes3(int[] nums) {
// **** traverse nums array - O(n) ****
for (int lastNonZeroNdx = 0, i = 0; i < nums.length; i++) {
// **** swap non-zero element with zero ****
if (nums[i] != 0) {
swap(nums, i, lastNonZeroNdx++);
// ???? ????
System.out.println("<<< nums: " + Arrays.toString(nums));
}
}
}
In this implementation of the function of interest we use a single loop and keep track of two indices. One is the current one used to traverse the array and the second holds the position of the last non-zero value.
/**
* Auxiliary function.
*/
private static void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
In several implementations we use an auxiliary function to swap values in the `nums` array.
/**
* Given an integer array nums, move all 0's to the end of it
* while maintaining the relative order` of the non-zero elements.
*
* 74 / 74 test cases passed.
* Status: Accepted
* Runtime: 1 ms
* Memory Usage: 40.6 MB
*
* Runtime: O(n) - Space: O(1)
*/
public static void moveZeroes(int[] nums) {
// **** initialization ****
int f = 0;
int s = 0;
int len = nums.length;
// **** traverse the array - O(n) ****
while (f < len) {
// **** skip zero value ****
if (nums[f] == 0) {
f++;
}
// **** swap non-zero values ****
else {
swap(nums, s++, f++);
// ???? ????
System.out.println("<<< nums: " + Arrays.toString(nums));
}
}
}
This is the final implementation. We also use a couple indices and a main loop. As I mentioned earlier, all implementations do the same but as we progress, the implementations are slightly more efficient. Note that the last three implementations run about the same.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
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., HackerRank, LeetCode).
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 toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John