283. Move Zeroes Easy

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:
Input: nums = [0]
Output: [0]

Approach

Input: An array nums

Output: Move 0 values to the end of the array while maintaining relative order

This is a Fast & Slow Pointers problem.

We can use a slow pointer pointing to the first number, regardless of whether it is a 0 or not.

Then, use a fast pointer to traverse the array from the beginning. When the fast pointer points to a non-zero number (including when both pointers point to the same number), swap the values of the fast and slow pointers, and then move the slow pointer.

Since the fast pointer skips when it encounters a 0, the fast pointer will inevitably get ahead of the slow pointer. The slow pointer will then pause on the 0. At this point, swapping the numbers effectively moves the 0 to the position of the fast pointer.

Implementation

python

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left = 0  # Slow pointer, indicating the position where the next non-zero element should be placed

        # right is the fast pointer, iterating through the array from start to finish
        for right in range(len(nums)):
            # Only process when the current element is not 0
            if nums[right] != 0:
                # Swap the elements at the current left and right positions
                # This puts the non-zero element at the left position, and moves the 0 from the left position to the right
                nums[left], nums[right] = nums[right], nums[left]
                
                # Move the slow pointer to prepare for the next non-zero element
                left += 1

javascript

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let left = 0;

    for (let right in nums) {
        if (nums[right] !== 0) {
            [nums[left], nums[right]] = [nums[right], nums[left]]
            left ++;
        }
    }
};

Complexity Analysis

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

Links

283. Move Zeroes (English)283. 移动零 (Chinese)