Definition
- Two-pointer compaction – a write pointer tracks where the next non-zero goes, and a scan pointer walks the entire array.
- Stability – the non-zero values keep their original relative order, making this a stable partition.
- In-place – no extra array is allocated; only two index variables are used.
- Two-pass version – pass 1 copies non-zeros forward; pass 2 fills the tail with zeros.
- One-pass swap version – swaps non-zeros into position as it scans, moving zeros rightward.
The National Bank of India has a row of settlement slots for Rajesh's day where some carry a real amount and some are empty (zero). The bank wants all real amounts compacted to the front in the same order they occurred, with the empty slots pushed to the back. A clerk keeps one finger on the next front slot and scans every slot; each real amount is slid forward, and whatever is left becomes empty.
Understanding the Concepts
What is the problem?
Given an array of integers, move all zeros to the end while preserving the relative order of the non-zero elements. The operation must be done in place with O(1) extra space.
At the National Bank of India, Rajesh's daily settlement has real amounts scattered with empty (zero) slots. The reconciliation system needs all real amounts at the front in their original order.
package com.bank.core;
import java.util.Arrays;
public class MoveZerosDemo {
public static void main(String[] args) {
int[] settlements = {500, 0, 300, 0, 0, 700, 100, 0};
System.out.println("Before: " + Arrays.toString(settlements));
moveZeros(settlements);
System.out.println("After: " + Arrays.toString(settlements));
}
static void moveZeros(int[] arr) {
int write = 0;
for (int scan = 0; scan < arr.length; scan++) {
if (arr[scan] != 0) {
arr[write++] = arr[scan];
}
}
while (write < arr.length) {
arr[write++] = 0;
}
}
}
Before: [500, 0, 300, 0, 0, 700, 100, 0]
After: [500, 300, 700, 100, 0, 0, 0, 0]
How does the two-pass write-and-fill approach work?
Pass 1: a write index starts at 0 and a scan index walks the entire array. Each time the scan finds a non-zero value, it copies it to the write position and advances the write pointer. After this pass, the first write positions hold all non-zero values in their original order.
Pass 2: fill every position from the write index to the end with zero.
static void moveZerosTwoPass(int[] arr) {
// Pass 1: compact non-zeros to the front
int write = 0;
for (int scan = 0; scan < arr.length; scan++) {
if (arr[scan] != 0) {
arr[write] = arr[scan];
write++;
}
}
// Pass 2: fill remaining with zeros
for (int i = write; i < arr.length; i++) {
arr[i] = 0;
}
}
How does the one-pass swap variant work?
Instead of a fill pass, swap each non-zero value with the value at the write position. This moves zeros rightward as you go. It does more writes than the fill version when zeros are frequent because of the swaps.
static void moveZerosSwap(int[] arr) {
int write = 0;
for (int scan = 0; scan < arr.length; scan++) {
if (arr[scan] != 0) {
int temp = arr[write];
arr[write] = arr[scan];
arr[scan] = temp;
write++;
}
}
}
package com.bank.core;
import java.util.Arrays;
public class SwapVariantDemo {
public static void main(String[] args) {
int[] a = {0, 0, 1, 0, 3, 12};
System.out.println("Before: " + Arrays.toString(a));
moveZerosSwap(a);
System.out.println("After: " + Arrays.toString(a));
}
}
Before: [0, 0, 1, 0, 3, 12]
After: [1, 3, 12, 0, 0, 0]
Why is stability important?
Stability means the non-zero values keep their original relative order. Both the write-and-fill and swap approaches preserve order because they process elements left to right and never reorder two non-zeros relative to each other. A two-ends approach that swaps from both ends would be faster at moving zeros but would scramble the non-zero order.
// WRONG: two-ends swap breaks order
static void moveZerosWrong(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
if (arr[left] == 0 && arr[right] != 0) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
if (arr[left] != 0) left++;
if (arr[right] == 0) right--;
}
}
// Input: [500, 0, 300, 0, 0, 700, 100, 0]
// Output: [500, 100, 300, 700, 0, 0, 0, 0] <-- 100 moved before 300!
How does this work with BigDecimal for money?
For banking, amounts are BigDecimal and zero is checked with signum() rather than ==. The same algorithm applies with the type change.
package com.bank.core;
import java.math.BigDecimal;
import java.util.Arrays;
public class MoveZerosBigDecimal {
static void moveZeros(BigDecimal[] arr) {
int write = 0;
for (int scan = 0; scan < arr.length; scan++) {
if (arr[scan].signum() != 0) {
arr[write++] = arr[scan];
}
}
while (write < arr.length) {
arr[write++] = BigDecimal.ZERO;
}
}
public static void main(String[] args) {
BigDecimal[] amounts = {
new BigDecimal("500.00"), BigDecimal.ZERO,
new BigDecimal("300.00"), BigDecimal.ZERO,
new BigDecimal("700.00")
};
System.out.println("Before: " + Arrays.toString(amounts));
moveZeros(amounts);
System.out.println("After: " + Arrays.toString(amounts));
}
}
Before: [500.00, 0, 300.00, 0, 700.00]
After: [500.00, 300.00, 700.00, 0, 0]
How does this generalize to a stable partition?
The same pattern is a stable partition around any predicate, not just zero. Replace the non-zero test with any condition and you push all failing elements to the end while keeping the passing ones in order. This is a reusable building block.
package com.bank.core;
import java.util.Arrays;
public class StablePartition {
// Partition: move all negative values to the end, keep order
static void partitionPositive(int[] arr) {
int write = 0;
for (int scan = 0; scan < arr.length; scan++) {
if (arr[scan] >= 0) {
arr[write++] = arr[scan];
}
}
// In real use, store the negatives in a temp buffer
// This simplified version just demonstrates the pattern
while (write < arr.length) {
arr[write++] = -1; // placeholder
}
}
public static void main(String[] args) {
int[] arr = {3, -1, 5, -2, 0, -4, 7};
System.out.println("Before: " + Arrays.toString(arr));
partitionPositive(arr);
System.out.println("After: " + Arrays.toString(arr));
}
}
What is the self-write optimization?
If the array is mostly non-zero, the write pointer and scan pointer move together, causing the algorithm to write a value back onto itself. Skipping the store when write equals scan avoids redundant writes and slightly reduces memory traffic on large arrays.
static void moveZerosOptimized(int[] arr) {
int write = 0;
for (int scan = 0; scan < arr.length; scan++) {
if (arr[scan] != 0) {
if (write != scan) {
arr[write] = arr[scan];
}
write++;
}
}
while (write < arr.length) {
arr[write++] = 0;
}
}
What are the edge cases?
Edge cases include an empty array, an array with no zeros, an array that is all zeros, and a single-element array. All are handled correctly by the write-and-fill approach without special checks.
package com.bank.core;
import java.util.Arrays;
public class MoveZerosEdgeCases {
public static void main(String[] args) {
int[] empty = {};
int[] noZeros = {1, 2, 3};
int[] allZeros = {0, 0, 0};
int[] single = {0};
moveZeros(empty); System.out.println(Arrays.toString(empty));
moveZeros(noZeros); System.out.println(Arrays.toString(noZeros));
moveZeros(allZeros); System.out.println(Arrays.toString(allZeros));
moveZeros(single); System.out.println(Arrays.toString(single));
}
static void moveZeros(int[] arr) {
int w = 0;
for (int s = 0; s < arr.length; s++) if (arr[s] != 0) arr[w++] = arr[s];
while (w < arr.length) arr[w++] = 0;
}
}
[]
[1, 2, 3]
[0, 0, 0]
[0]
What should a senior engineer know?
- Write count comparison. The two-pass version writes each non-zero once and each trailing zero once. The swap version writes each swap pair, which is more writes when zeros are frequent but fewer when zeros are rare.
- Predicate generalization. This is the foundation of stable partition algorithms used in sorting and data pipelines.
- In-place constraint. Allocating a second array and filtering is trivially correct but disqualifying for the interview, since the whole point is to demonstrate in-place modification.
- Memory traffic. On very large arrays in batch processing, the self-write optimization measurably reduces cache-line flushes.
Visual Overview
Input: [500, 0, 300, 0, 0, 700, 100, 0]
Pass 1 (write-and-fill):
scan=0: 500 != 0 -> arr[0]=500, write=1
scan=1: 0 == 0 -> skip
scan=2: 300 != 0 -> arr[1]=300, write=2
scan=3: 0 == 0 -> skip
scan=4: 0 == 0 -> skip
scan=5: 700 != 0 -> arr[2]=700, write=3
scan=6: 100 != 0 -> arr[3]=100, write=4
scan=7: 0 == 0 -> skip
After pass 1: [500, 300, 700, 100, ?, ?, ?, ?] write=4
Pass 2 (fill zeros):
arr[4]=0, arr[5]=0, arr[6]=0, arr[7]=0
Result: [500, 300, 700, 100, 0, 0, 0, 0]
Key Takeaway
Moving all zeros to the end while preserving order is a two-pointer in-place algorithm. I keep a write pointer for the next front position and scan the whole array. Every non-zero value I find gets placed at the write position, and after the scan I fill the remaining positions with zeros. It runs in O(n) time and O(1) space.
The requirement I never lose sight of is stability: the non-zero values must keep their original relative order. Both the write-and-fill and the swap approaches preserve order because they process left to right and never reorder two non-zeros. A faster two-ends approach would scramble the order, which breaks the requirement.
The pattern generalizes beyond zeros. It is really a stable partition around a predicate: replace the non-zero test with any condition and the same code pushes failing elements to the end while keeping the rest in order. For money at the National Bank of India, I use BigDecimal and test with signum() rather than ==.
A small but important optimization skips the store when the write and scan pointers are equal, avoiding redundant self-writes on a mostly-non-zero array. This reduces memory traffic on large batch arrays where the real data far outnumbers the zeros.
Remember one sentence: a write pointer collects non-zeros at the front in order, the tail is filled with zeros, and the result is a stable in-place partition in linear time.
---