DSA-019 · Stable read/write compaction then zero fill
Move Zeroes
Intermediate · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 29528 deterministic checks. Learner drafts are not executed.
Understand the problem
Move every zero to the end of an integer array in place, preserving the relative order of all nonzero values.
- nums is non-null with 0–100,000 signed int values. Zero means integer value 0; negative and extreme values are ordinary nonzero entries.
- Return void and keep the same array object. The final prefix is exactly the original nonzero subsequence in encounter order, followed by exactly the original number of zeros.
- The whole output array is specified. Use O(1) auxiliary space; stable order of nonzeros is required. The implementation may perform redundant writes and does not promise a minimum write count.
Examples
Input:
[0,1,0,3,12]
Output:[1,3,12,0,0]The surviving sequence 1,3,12 retains encounter order.
Input:
[0,-2,0,-1]
Output:[-2,-1,0,0]Negative values are preserved, not filtered.
Before you start
- Array indexing and inclusive pointer bounds
- Loop invariants and Java value versus reference semantics
Recognize the structure
This is stable filtering with a padded output. Sorting would reorder surviving values. A write pointer records the nonzero subsequence while a read pointer walks untouched future input.
Try before revealing
Hint 1
Treat nonzeros as the subsequence to retain.
Hint 2
Can a write position ever get ahead of the read position?
Hint 3
Compact nonzeros first; fill the remaining suffix with zero.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Build an initialized output buffer
Allocate n zeros, append each nonzero, and copy the buffer back. For [0,4,0,2], append 4 at output[0] and 2 at output[1]; remaining zero-initialized cells produce [4,2,0,0]. This is O(n) time and O(n) auxiliary space; compaction removes the temporary buffer.
Improve the baseline
Gather retained values
Set write=0. For each read position, emit its value at write only when it is nonzero, then increment write.
Prove overwrite safety
Before processing read, write≤read. Any emission changes a consumed slot or the current slot and cannot erase a future nonzero.
Fill only after discovery
Once the entire source is read, [0,write) is the stable nonzero subsequence. Fill [write,n) with zero. Clearing earlier during discovery could destroy an unread source.
Why it is correct
Processed-prefix invariant
Before each read, the output prefix before write is exactly the nonzero subsequence of the original processed positions, in original order. Unread positions have not changed.
Stable extension
A zero extends the processed region without changing the output. A nonzero appends one value at the next output position. Since appending follows read order, stability is preserved.
Final suffix
After the scan, write is the nonzero count. There are n-write original zeros. Filling exactly that many remaining positions restores their multiplicity and completes the specified array.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
public final class Solution {
public static void moveZeroes(int[] nums) {
int write = 0;
for (int read = 0; read < nums.length; read++) {
if (nums[read] != 0) nums[write++] = nums[read];
}
while (write < nums.length) nums[write++] = 0;
}
public static void baseline(int[] nums) {
int[] output = new int[nums.length];
int write = 0;
for (int value : nums) if (value != 0) output[write++] = value;
System.arraycopy(output, 0, nums, 0, nums.length);
}
}
Read the meaningful blocks
Nonzero predicate
nums[read]!=0 retains every signed nonzero; testing >0 would silently drop negatives.
Separate scan and fill
The suffix is safe to clear only after no unread source remains.
Write pointer reuse
The fill increments write through n; the earlier nonzero count is implicit at the boundary before fill, not needed by this void API.
Complexity
O(n) time for one full read scan and at most n zero writes. O(1) auxiliary space; the output is the original array.
The buffer baseline is O(n) time and O(n) storage. Swap-based approaches can reduce writes on some inputs, but stability and overwrite safety still need separate proofs.
Exact-state walkthroughs
Reveal normal and boundary traces
Stable compaction then suffix fill
Input: [0,1,0,3,12] · Final state: [1,3,12,0,0]
Step 1 of 9: Begin with an empty meaningful prefix.
write is the number of retained values from the processed original prefix.
- 0: 0
- 1: 1
- 2: 0
- 3: 3
- 4: 12
| Variable | Value |
|---|---|
| values | [0,1,0,3,12] |
| write | 0 |
| prefix | [] |
See the affected Java block
1 public final class Solution { 2 public static void moveZeroes(int[] nums) { 3 int write = 0; 4 for (int read = 0; read < nums.length; read++) { 5 if (nums[read] != 0) nums[write++] = nums[read]; 6 } 7 while (write < nums.length) nums[write++] = 0; 8 } 9 public static void baseline(int[] nums) { 10 int[] output = new int[nums.length]; 11 int write = 0; 12 for (int value : nums) if (value != 0) output[write++] = value; 13 System.arraycopy(output, 0, nums, 0, nums.length); 14 } 15 } 16
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with an empty meaningful prefix.
write is the number of retained values from the processed original prefix.
- values
[0,1,0,3,12]- write
0- prefix
[]
- Skip this occurrence.
The meaningful prefix equals the retained original subsequence; writes cannot reach beyond the current read index.
- values
[0,1,0,3,12]- read
0- value
0- kept
false- write
0- prefix
[]
- Append this retained value.
The meaningful prefix equals the retained original subsequence; writes cannot reach beyond the current read index.
- values
[1,1,0,3,12]- read
1- value
1- kept
true- write
1- prefix
[1]
- Skip this occurrence.
The meaningful prefix equals the retained original subsequence; writes cannot reach beyond the current read index.
- values
[1,1,0,3,12]- read
2- value
0- kept
false- write
1- prefix
[1]
- Append this retained value.
The meaningful prefix equals the retained original subsequence; writes cannot reach beyond the current read index.
- values
[1,3,0,3,12]- read
3- value
3- kept
true- write
2- prefix
[1,3]
- Append this retained value.
The meaningful prefix equals the retained original subsequence; writes cannot reach beyond the current read index.
- values
[1,3,12,3,12]- read
4- value
12- kept
true- write
3- prefix
[1,3,12]
- Fill one remaining suffix position with zero.
All source values have been read, so suffix writes cannot destroy unread data.
- values
[1,3,12,0,12]- write
4- phase
"zero fill"
- Fill one remaining suffix position with zero.
All source values have been read, so suffix writes cannot destroy unread data.
- values
[1,3,12,0,0]- write
5- phase
"zero fill"
- Final in-place state; Java returns void.
All required values have been finalized under the declared contract.
- result
[1,3,12,0,0]
No zero already needs moving
Input: [2,-1] · Final state: [2,-1]
Step 1 of 4: Begin with an empty meaningful prefix.
write is the number of retained values from the processed original prefix.
- 0: 2
- 1: -1
| Variable | Value |
|---|---|
| values | [2,-1] |
| write | 0 |
| prefix | [] |
See the affected Java block
1 public final class Solution { 2 public static void moveZeroes(int[] nums) { 3 int write = 0; 4 for (int read = 0; read < nums.length; read++) { 5 if (nums[read] != 0) nums[write++] = nums[read]; 6 } 7 while (write < nums.length) nums[write++] = 0; 8 } 9 public static void baseline(int[] nums) { 10 int[] output = new int[nums.length]; 11 int write = 0; 12 for (int value : nums) if (value != 0) output[write++] = value; 13 System.arraycopy(output, 0, nums, 0, nums.length); 14 } 15 } 16
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with an empty meaningful prefix.
write is the number of retained values from the processed original prefix.
- values
[2,-1]- write
0- prefix
[]
- Append this retained value.
The meaningful prefix equals the retained original subsequence; writes cannot reach beyond the current read index.
- values
[2,-1]- read
0- value
2- kept
true- write
1- prefix
[2]
- Append this retained value.
The meaningful prefix equals the retained original subsequence; writes cannot reach beyond the current read index.
- values
[2,-1]- read
1- value
-1- kept
true- write
2- prefix
[2,-1]
- Final in-place state; Java returns void.
All required values have been finalized under the declared contract.
- result
[2,-1]
Test the contract
Input:
[]
Output:[]No reads or writes.
Input:
[0,0]
Output:[0,0]Empty nonzero prefix.
Input:
[2,1]
Output:[2,1]Nonzero order is not sorted.
Input:
[0,-1,0,2,0]
Output:[-1,2,0,0,0]Stable signed subsequence.
Common mistakes and counterexamples
Swap each zero with the last value
Counterexample: [0,1,2] can become [2,1,0], violating nonzero order.
Compact nonzeros from left to right.
Keep only positive numbers
Counterexample: [0,-2,1] must retain -2.
Use !=0.
Clear the source during discovery
Counterexample: A premature suffix fill on [0,1] can erase the unread 1.
Complete the read scan before filling the suffix.
Follow-ups
Reduce unnecessary writes.
Skip nums[write]=nums[read] when write==read, or use carefully ordered swaps. Compare actual write counts; linear time alone says nothing about write optimality.
Stable partition arbitrary records.
Compacting retained records is easy, but retaining both partitions in original order generally requires more storage or more complex in-place algorithms. Zero payloads are interchangeable in this contract.
Make it streaming.
Emit nonzeros as they arrive while counting zeros, then emit that many zeros at end of stream. A source with no known end cannot finalize its zero suffix yet.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 85/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.