Move Zeroes
Move every 0 to the end of an array in place, keeping the other numbers in their order.
In an array of integers numsnums
Example 1
Output: [1, 3, 12, 0, 0]
Example 2
Output: [0]
The Idea
Picture five boxes in a row on a shelf, holding 0, 1, 0, 3 and 12. A 0 is an empty box. You want the full boxes at the front, in the same order as before, and the empty ones pushed to the back. For Example 1 that gives 1, 3, 12, followed by the two zeros.
The boxes cannot leave the shelf, though. The array has to be rearranged inside itself, with no second array to copy into. One way is to take out each 0, shift every number after it one place left, and put the 0 at the end. But then each 0 costs a pass over the rest of the array. Can every number reach its place in a single read of the array?
Think about where each non-zero number should end up. The first non-zero belongs at index 0, the second at index 1, and so on. So while reading the array from left to right, only one thing needs remembering: the index where the next non-zero belongs. Call it slowfast
When fastfastslowslow
In the top row, labelled "before the swap", fastslowfastslowslow
So the array always has three parts: the non-zeros so far at the front, then the zeros already read, then the numbers fastfast
Two indexes that walk through an array in the same direction, one reading and one marking where to write, are a form of the two-pointer technique. Because one of them can only lag behind the other, they are often called slow and fast pointers.
Solution Approach
Turning that idea into code means settling three things: what to do with a non-zero, how the order of the numbers is kept, and what happens when there is no 0 to swap with.
Swapping a non-zero forward
What should happen when fastnums[slow]slowfast - 1slowfastslowslowfast
The swap is also what makes one pass enough. Shifting the rest of the array left for every 0 can take about n steps per 0, where n is the length of the array. With many zeros, that grows like n². Here each number is read once and swapped at most once.
Keeping the order
Does the swap mix up the non-zeros? No. fast
Arrays without a 0 to swap
What if the array has no zeros at all, like [1, 2, 3]slowfast[0]
Java Solution
The method moveZeroes
- First, set
to 0, the index where the next non-zero belongs.slow - Read the array with a
loop, in whichfor goes from 0 to the last index.fast - When
is not 0, swap it withnums[fast] through a temporary variablenums[slow] , then movetmp one place right. When it is 0, do nothing, and the loop movesslow on.fast - When the loop ends, the non-zeros fill the front of
in their old order, and the zeros fill the rest. The method returns nothing, because it has changednums itself.nums
The mainrun
import java.util.Arrays;
public class MoveZeroes {
public static void moveZeroes(int[] nums) {
int slow = 0; // where the next non-zero belongs
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 0) {
int tmp = nums[slow]; // swap the non-zero forward;
nums[slow] = nums[fast]; // a zero (if any) moves back
nums[fast] = tmp;
slow++;
}
}
}
static void run(int[] nums) {
String before = Arrays.toString(nums);
moveZeroes(nums);
System.out.println(before + " -> " + Arrays.toString(nums));
}
public static void main(String[] args) {
run(new int[] {0, 1, 0, 3, 12});
run(new int[] {0});
run(new int[] {1, 2, 3});
run(new int[] {0, 0, 1});
run(new int[] {4, 0, -5, 0, 0, 4});
run(new int[] {});
}
}
Running it prints:
[0, 1, 0, 3, 12] -> [1, 3, 12, 0, 0]
[0] -> [0]
[1, 2, 3] -> [1, 2, 3]
[0, 0, 1] -> [1, 0, 0]
[4, 0, -5, 0, 0, 4] -> [4, -5, 4, 0, 0, 0]
[] -> []
Look at the fourth line: [0, 0, 1][1, 0, 0]slowfast
The fifth line turns [4, 0, -5, 0, 0, 4][4, -5, 4, 0, 0, 0][1, 2, 3]
The original implementation,
Complexity
The work is a single pass of fast
- Time: O(n), for an array of n numbers, because the
loop reads each of the n numbers once and does at most one swap of three assignments for each.for - Space: O(1). The numbers are rearranged inside
, and onlynums ,slow andfast are used.tmp
The same slow and fast pointers solve slow