1. Overview
When we work with arrays in Java, one common task is rearranging arrays to optimize their structure. One such scenario involves moving zeros to the end of an array.
In this tutorial, we’ll explore different approaches to achieve this task using Java.
2. Introduction to the Problem
Before we dive into the implementation, let’s first understand the requirements of this problem.
Our input is an array of integers. We aim to rearrange the integers so that all zeros are moved to the end of the array. Further, the order of those non-zero elements must be retained.
An example can help us understand the problem quickly. Let’s say we’re given an integer array:
[ 42, 2, 0, 3, 4, 0 ]
After we rearrange its elements, we expect to obtain an array equivalent to the following as the result:
static final int[] EXPECTED = new int[] { 42, 2, 3, 4, 0, 0 };
Next, we’ll cover two approaches to solving the problem. We’ll also briefly discuss their performance characteristics.
3. Using an Additional Array
To tackle the problem, the first idea that comes up might be to use an additional array.
Let’s say we create a new array and call it result. This array is initialized with the same length as the input array, and all its elements are set to zero.
Next, we traverse the input array. Whenever a non-zero number is encountered, we update the corresponding element in the result array accordingly.
Let’s implement this idea:
int[] array = new int[] { 42, 2, 0, 3, 4, 0 };
int[] result = new int[array.length];
int idx = 0;
for (int n : array) {
if (n != 0) {
result[idx++] = n;
}
}
assertArrayEquals(EXPECTED, result);
As we can see, the code is pretty straightforward. Two things are worth mentioning:
In this solution, we walk through the input array only once. Therefore, this approach has linear time complexity: O(n). However, as it duplicates the input array, its space complexity is O(n).
Next, let’s explore how to improve this solution to achieve an in-place arrangement to maintain a constant space complexity of O(1).
4. In-Place Arrangement with Linear Time Complexity
Let’s first revisit the “initializing a new array” approach. We maintained a non-zero-pointer (idx) on the new array so that we know which element in the result array needs to be updated once a non-zero value is detected in the original array.
In fact, we can set the non-zero pointer on the input array. In this way, when we iterate through the input array, we can shift non-zero elements to the front, maintaining their relative order. After completing the iteration, we’ll fill the remaining positions with zeros.
Let’s take our input array as an example to understand how this algorithm works:
Iteration pointer: v
Non-zero-pointer: ^
v
42, 2, 0, 3, 4, 0
^ (replace 42 with 42)
v
42, 2, 0, 3, 4, 0
^ (replace 2 with 2)
v
42, 2, 0, 3, 4, 0
^
v
42, 2, 3, 3, 4, 0
^ (replace 0 with 3)
v
42, 2, 3, 4, 4, 0
^ (replace 3 with 4)
v
42, 2, 3, 4, 4, 0
^
The final step: Fill 0s to the remaining positions:
v
42, 2, 3, 4, 0, 0
^
Next, let’s implement this logic:
int[] array = new int[] { 42, 2, 0, 3, 4, 0 };
int idx = 0;
for (int n : array) {
if (n != 0) {
array[idx++] = n;
}
}
while (idx < array.length) {
array[idx++] = 0;
}
assertArrayEquals(EXPECTED, array);
As we can see, no additional array is introduced in the above code. The non-zero-pointer idx keeps track of the position where non-zero elements should be placed. During the iteration, if the current element is non-zero, we move it to the front and increment the pointer. After completing the iteration, we fill the remaining positions with zeros using a while loop.
This approach performs an in-place rearrangement. That is to say, no extra space is required. Therefore, its space complexity is O(1).
In the worst-case scenario where all elements in the input array are zeros, the downside is that the idx pointer remains stationary after the iteration. Consequently, the subsequent while loop will traverse the entire array once more. Despite this, since the iteration is executed a constant number of times, the overall time complexity remains unaffected at O(n).
5. Conclusion
In this article, we explored two methods for relocating zeros to the end of an integer array. Additionally, we discussed their performance in terms of time and space complexities.
As always, the complete source code for the examples is available over on GitHub.
