☕ DSA Java Articles

Topics › Arrays › Easy

Move Zeros to End

Easy TUF ID 46 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array of integers nums. Move every 0 to the end of the array in place, while keeping the non-zero elements in their original relative order.

Constraints: 0 ≤ n ≤ 10^5, values fit in a 32-bit signed integer and may be negative.

Example 1

nums = [0, 1, 0, 3, 12]
after  = [1, 3, 12, 0, 0]        // 1, 3, 12 keep their order; both zeros go to the back

Example 2

nums = [1, 0, 2, 3, 0, 4, 0, 1]
after  = [1, 2, 3, 4, 1, 0, 0, 0]

Example 3

nums = [0, 0, 0]
after  = [0, 0, 0]               // nothing to move

Two requirements fight each other: “in place” says do not allocate, and “keep the relative order” rules out the cheap trick of swapping every zero with the last element. The resolution is the two-pointer partition, one of the most reused ideas in array problems.

Approach 1: Brute force, collect the non-zeros

Intuition. Pull every non-zero value out into a list, in order. Write the list back into the front of the array, and fill whatever remains with zeros. Order is preserved because the list is built left to right, and the result is correct because the number of zeros is exactly n - (number of non-zeros).

Algorithm.

  1. Append each non-zero x to a list nonZero.
  2. Write nonZero[0..m-1] into nums[0..m-1].
  3. Set nums[m..n-1] to 0.
static void bruteForce(int[] nums) {
    int n = nums.length;
    List<Integer> nonZero = new ArrayList<>();
    for (int x : nums) if (x != 0) nonZero.add(x);
    int i = 0;
    for (int x : nonZero) nums[i++] = x;
    while (i < n) nums[i++] = 0;
}

Complexity. Time O(n): three linear passes. Space O(n) for the list in the worst case (no zeros at all), plus the cost of boxing each int to an Integer.

This is linear already; the only thing wrong with it is the extra memory, and a problem that says “in place” is asking you to remove it.

Approach 2: Optimal, swap each non-zero into the leftmost zero

Intuition. Keep a pointer j on the leftmost zero. Scan with i to the right of it. Whenever nums[i] is non-zero, swap it with nums[j]: the non-zero moves left into the zero’s slot, the zero moves right. Then advance j by one.

Why is nums[j] guaranteed to be a zero after j++? Because of an invariant: every slot from j up to i - 1 is a zero. Initially j is the first zero and i = j + 1, so the range j..i-1 is just {j}. Each time i passes a zero, the range grows and stays all-zero. Each time i finds a non-zero and swaps, the zero from j lands at i, so after j++ the range j..i is still all zeros. Non-zeros are only ever moved leftwards past a block of zeros, never past another non-zero, so their relative order is untouched.

Algorithm.

  1. Find j, the index of the first zero. If there is none, return.
  2. For i from j + 1 to n - 1: if nums[i] != 0, swap nums[i] and nums[j], then j++.
static void optimal(int[] nums) {
    int n = nums.length;
    int j = -1;                                  // index of the leftmost zero, -1 while none is found
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) { j = i; break; }
    }
    if (j == -1) return;                         // no zero anywhere: nothing to move
    for (int i = j + 1; i < n; i++) {
        if (nums[i] != 0) {
            int t = nums[i];                     // every slot between j and i is a zero
            nums[i] = nums[j];
            nums[j] = t;
            j++;
        }
    }
}

Dry run on nums = [1, 0, 2, 3, 0, 4, 0, 1]. The first zero is at index 1, so j = 1.

i nums[i] action array j after
2 2 swap(2, 1) [1, 2, 0, 3, 0, 4, 0, 1] 2
3 3 swap(3, 2) [1, 2, 3, 0, 0, 4, 0, 1] 3
4 0 skip [1, 2, 3, 0, 0, 4, 0, 1] 3
5 4 swap(5, 3) [1, 2, 3, 4, 0, 0, 0, 1] 4
6 0 skip [1, 2, 3, 4, 0, 0, 0, 1] 4
7 1 swap(7, 4) [1, 2, 3, 4, 1, 0, 0, 0] 5

Complexity. Time O(n): the first loop and the second together visit each index at most twice. Space O(1).

Approach 3: Optimal, write pointer then zero-fill

Intuition. A cleaner way to see the same thing: w is the index where the next non-zero should be written. Scan every element; copy each non-zero to nums[w] and advance w. Because w never runs ahead of the read position, no unread element is overwritten. When the scan ends, nums[0..w-1] is the compacted sequence of non-zeros and everything from w onwards should be zero, so fill it.

Compared with the swap version this does fewer writes when there are few zeros (a non-zero that is already in place is copied onto itself, not swapped twice) and does not need the preliminary search for the first zero. It is also exactly the pattern used by Remove duplicates from Sorted array.

Algorithm.

  1. w = 0.
  2. For each x in nums: if x != 0, nums[w++] = x.
  3. While w < n: nums[w++] = 0.
static void optimalWritePointer(int[] nums) {
    int w = 0;                                   // next slot that should receive a non-zero
    for (int x : nums) {
        if (x != 0) nums[w++] = x;               // w <= current index, so nothing unread is overwritten
    }
    while (w < nums.length) nums[w++] = 0;
}

Complexity. Time O(n), space O(1).

A detail worth understanding: the enhanced for loop reads nums while the body writes into nums. This is safe because writes go to index w, which is always ≤ the index currently being read, so each element is read before any write could reach it.

Edge cases and pitfalls