Move Zeroes

This question is asked by Apple. Given an array of numbers, move all zeroes in the array to the end while maintaining the relative order of the other numbers.

Note: You must modify the array you're given (i.e., you cannot create a new array).

Example(s)

Example 1:

Input: nums = [3, 7, 0, 5, 0, 2]
Output: [3, 7, 5, 2, 0, 0]
Explanation:
- Move all zeros to the end
- Maintain relative order of non-zero elements: 3, 7, 5, 2

Example 2:

Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]
Explanation:
- Move zeros to the end
- Non-zero elements: 1, 3, 12 maintain their order

Example 3:

Input: nums = [0, 0, 1]
Output: [1, 0, 0]
Explanation:
- All zeros move to the end
- Single non-zero element: 1

Solution

The solution uses two pointers:

1. Slow pointer: Points to the next position for a non-zero element
2. Fast pointer: Scans through the array
3. Swap or copy: Move non-zero elements to the slow pointer position
4. Fill zeros: After processing, fill remaining positions with zeros

JavaScript Solution

JavaScript Solution - Two Pointers

/**
* Move all zeros to the end
* @param {number[]} nums - Input array (modified in-place)
* @return {void} - Modifies array in-place
*/
function moveZeroes(nums) {
let slow = 0; // Points to next position for non-zero element

// Move all non-zero elements to the front
for (let fast = 0; fast < nums.length; fast++) {
  if (nums[fast] !== 0) {
    // Swap or copy non-zero element to slow pointer position
    if (slow !== fast) {
      nums[slow] = nums[fast];
    }
    slow++;
  }
}

// Fill remaining positions with zeros
while (slow < nums.length) {
  nums[slow] = 0;
  slow++;
}
}

// Test cases
let nums1 = [3, 7, 0, 5, 0, 2];
moveZeroes(nums1);
console.log('Example 1:', nums1); 
// [3, 7, 5, 2, 0, 0]

let nums2 = [0, 1, 0, 3, 12];
moveZeroes(nums2);
console.log('Example 2:', nums2); 
// [1, 3, 12, 0, 0]

let nums3 = [0, 0, 1];
moveZeroes(nums3);
console.log('Example 3:', nums3); 
// [1, 0, 0]

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Solution - Two Pointers

from typing import List

def move_zeroes(nums: List[int]) -> None:
  """
  Move all zeros to the end (modifies array in-place)
  
  Args:
      nums: Input array (modified in-place)
  """
  slow = 0  # Points to next position for non-zero element
  
  # Move all non-zero elements to the front
  for fast in range(len(nums)):
      if nums[fast] != 0:
          # Swap or copy non-zero element to slow pointer position
          if slow != fast:
              nums[slow] = nums[fast]
          slow += 1
  
  # Fill remaining positions with zeros
  while slow < len(nums):
      nums[slow] = 0
      slow += 1

# Test cases
nums1 = [3, 7, 0, 5, 0, 2]
move_zeroes(nums1)
print('Example 1:', nums1)  
# [3, 7, 5, 2, 0, 0]

nums2 = [0, 1, 0, 3, 12]
move_zeroes(nums2)
print('Example 2:', nums2)  
# [1, 3, 12, 0, 0]

nums3 = [0, 0, 1]
move_zeroes(nums3)
print('Example 3:', nums3)  
# [1, 0, 0]

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Swap Approach)

Here's a version that swaps instead of copying:

JavaScript Swap

/**
 * Swap approach (slightly different)
 */
function moveZeroesSwap(nums) {
  let slow = 0;
  
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      // Swap non-zero element with slow pointer position
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      slow++;
    }
  }
}

Python Swap

def move_zeroes_swap(nums: List[int]) -> None:
    """
    Swap approach
    """
    slow = 0
    
    for fast in range(len(nums)):
        if nums[fast] != 0:
            # Swap non-zero element with slow pointer position
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

Complexity

• Time Complexity: O(n) - Where n is the length of the array. We make a single pass through the array.
• Space Complexity: O(1) - Only using a constant amount of extra space (two pointers).

Approach

The solution uses two pointers:

1. Slow pointer:

   • Points to the next position where a non-zero element should be placed
   • Increments only when we place a non-zero element

2. Fast pointer:

   • Scans through the entire array
   • Finds non-zero elements

3. Move non-zeros:

   • When fast pointer finds a non-zero, move it to slow pointer position
   • Increment slow pointer

4. Fill zeros:

   • After processing all elements, fill remaining positions (from slow to end) with zeros

Key Insights

• Two pointers: Slow tracks position for non-zeros, fast scans array
• In-place modification: No new array needed
• Relative order preserved: Non-zeros maintain their original order
• Fill zeros at end: After moving non-zeros, fill rest with zeros
• O(n) time: Single pass through array

Step-by-Step Example

Let's trace through Example 1: nums = [3, 7, 0, 5, 0, 2]

Initial: nums = [3, 7, 0, 5, 0, 2]
         slow = 0, fast = 0

fast = 0: nums[0] = 3 (non-zero)
  nums[0] = 3 (already in place)
  slow = 1

fast = 1: nums[1] = 7 (non-zero)
  nums[1] = 7 (already in place)
  slow = 2

fast = 2: nums[2] = 0 (zero)
  Skip, don't move slow
  slow = 2

fast = 3: nums[3] = 5 (non-zero)
  nums[2] = nums[3] = 5
  nums = [3, 7, 5, 5, 0, 2]
  slow = 3

fast = 4: nums[4] = 0 (zero)
  Skip, don't move slow
  slow = 3

fast = 5: nums[5] = 2 (non-zero)
  nums[3] = nums[5] = 2
  nums = [3, 7, 5, 2, 0, 2]
  slow = 4

After loop: slow = 4
Fill zeros from index 4 to end:
  nums[4] = 0
  nums[5] = 0
  nums = [3, 7, 5, 2, 0, 0]

Result: [3, 7, 5, 2, 0, 0]

Visual Representation

Example 1: nums = [3, 7, 0, 5, 0, 2]

Step 1: Move non-zeros to front
  slow=0: [3, 7, 0, 5, 0, 2] → 3 is non-zero, keep at index 0
  slow=1: [3, 7, 0, 5, 0, 2] → 7 is non-zero, keep at index 1
  slow=2: [3, 7, 0, 5, 0, 2] → 0 is zero, skip
  slow=2: [3, 7, 5, 5, 0, 2] → 5 is non-zero, move to index 2
  slow=3: [3, 7, 5, 2, 0, 2] → 0 is zero, skip
  slow=3: [3, 7, 5, 2, 0, 2] → 2 is non-zero, move to index 3

Step 2: Fill zeros at end
  [3, 7, 5, 2, 0, 0]

Result: [3, 7, 5, 2, 0, 0]

Edge Cases

• All zeros: Array remains all zeros
• No zeros: Array remains unchanged
• Zeros at start: All moved to end
• Zeros at end: Already in correct position
• Single element: Works correctly
• All non-zeros: Array unchanged

Important Notes

• In-place modification: Must modify the given array
• Relative order: Non-zero elements maintain their original order
• Two passes: One to move non-zeros, one to fill zeros (or combine)
• O(1) space: Only using two pointers
• O(n) time: Single pass through array

Optimization: Single Pass

We can optimize to avoid the second pass by swapping:

function moveZeroesOptimized(nums) {
  let slow = 0;
  
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      // Swap (this automatically handles zeros)
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      slow++;
    }
  }
}

This swaps non-zeros with whatever is at slow position (could be zero or non-zero), eliminating the need to fill zeros separately.

Related Problems

• Remove Element: Similar two-pointer problem
• Remove Duplicates: Different two-pointer problem
• Partition Array: Similar partitioning problem
• Sort Colors: Different partitioning problem

Takeaways

• Two pointers efficiently move elements in-place
• Slow pointer tracks position for non-zeros
• Fast pointer scans for non-zero elements
• O(n) time with single pass
• O(1) space using only two pointers