Move Zeroes: Two pointers Pattern

Learning Outcome

After this lesson, you should be able to preserve the order of non-zero values while moving zeroes to the end in-place.

Problem Statement

Given an integer array nums, move all zeroes to the end while keeping the relative order of non-zero elements. Modify the array in-place.

Brute Force Approach

Create a temporary list of non-zero values, copy them back into the array, and fill the rest with zeroes.

This is clear, but it uses O(n) extra space. The interview usually expects in-place modification.

Optimized Approach

Use write as the position where the next non-zero value should go. Scan the array once. Whenever a non-zero value appears, write it at write and move write forward.

After all non-zero values are compacted at the front, fill the remaining positions with zeroes.

Exact Pseudocode

write = 0
for read from 0 to length(nums) - 1:
  if nums[read] != 0:
    nums[write] = nums[read]
    write = write + 1
while write < length(nums):
  nums[write] = 0
  write = write + 1
  

Reference Code

class Solution:
    def moveZeroes(self, nums):
        write = 0

        for value in nums:
            if value != 0:
                nums[write] = value
                write += 1

        while write < len(nums):
            nums[write] = 0
            write += 1
  

Sample Dry Run

Complexity

Edge Cases

• All zeroes.
• No zeroes.
• Zeroes already at the end.

Interview Checklist

• Preserve order of non-zero values.
• Do not allocate another array unless allowed.
• Remember to fill the tail with zeroes.

FAQs