Move Zeroes: definition
Move every zero to the end of an array while preserving the relative order of non-zero values. This problem is an example of the read/write two-pointer technique.
Task example: Move Zeroes
Given an integer array nums, move all zeros to the end in place. Keep the non-zero values in their original order. Modify nums itself; do not return a new array. The extra-space approach below is a comparison baseline and does not satisfy the no-extra-array requirement.
The array does not need to be sorted. Negative values and duplicates are allowed. The demos also accept an empty array.
Collect & fill: video explanation
nums = [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0]
Prefer reading? Follow the steps below.
- Create kept, an empty list. Scan nums from left to right. Append each non-zero value and skip each zero. This preserves non-zero order.
- Loop over every index i in nums. If i is smaller than len(kept), copy kept[i] into nums[i]. Otherwise, write zero.
- For [0, 1, 0, 3, 12], kept becomes [1, 3, 12]. Copy those values to the first three positions, then fill the last two positions with zeros.
Time complexity · O(n)
One scan collects values; one pass updates nums. Their work adds up to O(n), not O(n²).
Space complexity · O(n)
kept can contain all n values, so extra space is O(n). This baseline uses an extra array.
Two pointers: video explanation
nums = [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0]
Prefer reading? Follow the steps below.
- Set write = 0. Move read from left to right. write marks where the next non-zero value belongs.
- If nums[read] is non-zero, copy it to nums[write], then increment write. Skip zeros without advancing write.
- After the scan, the prefix contains [1, 3, 12] and write = 3. Fill nums[3] and nums[4] with zeros. The result is [1, 3, 12, 0, 0].
Why it works: write never goes ahead of read, so copying cannot destroy unread values. Scanning left to right preserves non-zero order. Fill the tail only after the scan finishes.
Time complexity · O(n)
read visits n positions, then the tail fill takes at most n steps. The loops are sequential, so total time is O(n).
Space complexity · O(1)
Only read and write are stored. Extra space is O(1). Compared with the baseline, time stays O(n) while extra space drops from O(n) to O(1).