Move Zeroes

How it works

Instead of copying values and then filling zeros separately, we can swap elements in a single pass. The left pointer marks the boundary between processed non-zero elements and unprocessed elements. When we encounter a non-zero element with the right pointer, we swap it with the element at the left pointer. This naturally pushes 0 to the right while keeping non-zero elements in their relative order.

Steps

1. Initialize l = 0 to track the swap position.
2. Iterate through the array with pointer r. For each non-zero element:
   • Swap nums[l] and nums[r].
   • Increment l.
3. After the loop, all non-zero elements are at the front and zeros are at the end.

Complexity

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

Things to watch for

Swapping When Pointers Are at the Same Position

When both pointers l and r point to the same non-zero element, swapping is unnecessary and wastes operations. While this does not affect correctness, adding a check like if (l != r) before swapping improves efficiency and avoids redundant writes, which can matter for performance-sensitive applications.

Disrupting Relative Order of Non-Zero Elements

The problem requires maintaining the relative order of non-zero elements. Some approaches incorrectly swap non-zero elements with each other or move them out of sequence. The two-pointer technique works because the left pointer only advances when a non-zero element is placed, ensuring all non-zero elements shift left in their original order while zeros naturally accumulate at the end.

from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l = 0
        for r in range(len(nums)):
            if nums[r]:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for (int l = 0, r = 0; r < nums.size(); r++) {
            if (nums[r]) {
                swap(nums[l++], nums[r]);
            }
        }
    }
};