Move Zeroes (LC 283)

Pattern: Two Pointers
Difficulty: Easy
Key Concept: Maintain a “write” position for the next non-zero while scanning with a “read” pointer (or compact with a single slow/fast index).

Problem Statement

Given an integer array nums, move all 0’s to the end of the array while maintaining the relative order of the non-zero elements.

Constraints: You must solve this in-place (modify the input array). Do not allocate another array for the final answer in the intended optimal solution.

Input: Integer array nums.
Output: nums rearranged so all zeros are at the end; non-zeros keep their relative order.

Example: nums = [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0].

1. Algorithm & Pseudocode

Brute force (extra array)

1. Create a new array ans of the same length.
2. Scan nums left to right; copy each non-zero to ans from the start.
3. Fill the remainder of ans with zeros.
4. Copy ans back into nums (if you are allowed a buffer; pure “extra array” solution returns ans).

(Interview note: if “in-place” is strict, this is not the final answer—but it shows the baseline idea.)

Optimal (in-place two pointers — “snowball” / partition style)

1. Let write = 0 (next index to place a non-zero).
2. For read from 0 to n-1:
   If nums[read] != 0:
     Swap nums[write] and nums[read]  (or assign nums[write] = nums[read] if using write-only variant)
     write++
3. Optionally: second pass to zero out from write to end (if you used assignment-only variant).

Common clean variant (swap):

write = 0
for read in 0 .. n-1:
  if nums[read] != 0:
    swap(nums, write, read)
    write++

After this, all non-zeros appear in order at the front; zeros are pushed to the right via swaps.

2. Step-by-Step Analysis (Beginner-Friendly)

What must stay the same?
The order of non-zero elements: [1, 3, 12] must stay 1 then 3 then 12.

Why not “sort”?
Sorting would destroy relative order among non-zeros. We only need to partition zeros to the back.

Brute force
Copy non-zeros to a fresh array in one pass, pad with zeros. Easy to reason about, but O(n) extra space.

Optimal
Think of write as “the front of the array that is already correct.” When read sees a non-zero, it belongs at write; swapping brings it there and bumps write. Zeros get swapped toward the right naturally. Each non-zero takes one swap into its correct relative slot.

Why swap instead of shifting?
Swapping is O(1) per operation; shifting the whole tail every time would be O(n²).

Java arrays
int[] is mutable and passed by reference—methods see the same array object, so in-place updates persist.

3. The Dry Run

Sample: nums = [0, 1, 0, 3, 12]
Algorithm: single pass with write and read, swap when nums[read] != 0.

Step	`read`	`write`	`nums` (after step)	Action
init	—	0	`[0, 1, 0, 3, 12]`	Start
1	0	0	`[0, 1, 0, 3, 12]`	`nums[0]==0` → no swap
2	1	0	`[1, 0, 0, 3, 12]`	non-zero: swap(0,1); `write`→1
3	2	1	`[1, 0, 0, 3, 12]`	zero at `read` 2 → skip
4	3	1	`[1, 3, 0, 0, 12]`	swap(1,3); `write`→2
5	4	2	`[1, 3, 12, 0, 0]`	swap(2,4); `write`→3

Final: [1, 3, 12, 0, 0].

Variable snapshot per iteration (compact):

`read`	`nums[read]`	swap?	`write` after
0	0	No	0
1	1	Yes	1
2	0	No	1
3	3	Yes	2
4	12	Yes	3

4. Java Solution

Brute Force

Idea: Use auxiliary array, copy non-zeros then zeros, copy back.

Time: O(n)
Space: O(n)

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int[] aux = new int[n];
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] != 0) {
                aux[j++] = nums[i];
            }
        }
        // remainder of aux is already 0 by default
        System.arraycopy(aux, 0, nums, 0, n);
    }
}

Optimal

Idea: write marks placement; swap non-zeros forward.

Time: O(n)
Space: O(1)

class Solution {
    public void moveZeroes(int[] nums) {
        int write = 0;
        for (int read = 0; read < nums.length; read++) {
            if (nums[read] != 0) {
                int tmp = nums[write];
                nums[write] = nums[read];
                nums[read] = tmp;
                write++;
            }
        }
    }
}

You can XOR-swap for integers without a temp variable, but a temp is clearer and avoids style/pitfall debates in interviews.

5. The “Java vs. Others” Edge

In-place on int[]: Java arrays are mutable objects; the method receives a reference, so changes are visible to the caller—similar to passing a pointer in C++.
Python often uses tuple unpacking for swap: nums[i], nums[j] = nums[j], nums[i]. In Java you typically use a temporary variable (or helper method).
System.arraycopy is a fast bulk copy when you use the brute-force “copy back” pattern.
Do not confuse with String: reversing or moving characters in a String requires a new object; here the problem is an int[], so swapping elements is natural.

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(n)	Extra array; easy to verify correctness
Optimal	O(n)	O(1)	Partition with `write`/`read` swaps; standard solution