Move Zeroes easy

Problem Statement

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]

Steps

The key idea is to use two pointers:

1. zero_ptr: Points to the index where the next zero should be placed. It starts at 0.
2. non_zero_ptr: Iterates through the array. It finds non-zero elements.

Whenever non_zero_ptr encounters a non-zero element, it swaps that element with the element at the zero_ptr index. Then both zero_ptr and non_zero_ptr are incremented. This ensures that all non-zero elements are moved to the beginning of the array while preserving their relative order. After processing the entire array, the remaining elements from zero_ptr to the end of the array are all zeros.

Explanation

The algorithm efficiently moves non-zero elements to the front of the array without needing extra space. The swapping operation maintains the relative order of the non-zero elements. The use of two pointers makes the algorithm linear in time complexity.

Code

def moveZeroes(nums):
    """
    Moves all 0's to the end of the array in-place.

    Args:
        nums: A list of integers.
    """
    zero_ptr = 0  # Pointer for placing zeros
    non_zero_ptr = 0  # Pointer for iterating through the array

    while non_zero_ptr < len(nums):
        if nums[non_zero_ptr] != 0:
            # Swap non-zero element with element at zero_ptr
            nums[zero_ptr], nums[non_zero_ptr] = nums[non_zero_ptr], nums[zero_ptr]
            zero_ptr += 1  # Move zero_ptr to the next position
        non_zero_ptr += 1  # Always move non_zero_ptr


# Example usage
nums1 = [0, 1, 0, 3, 12]
moveZeroes(nums1)
print(nums1)  # Output: [1, 3, 12, 0, 0]

nums2 = [0]
moveZeroes(nums2)
print(nums2)  # Output: [0]

nums3 = [0,0,1]
moveZeroes(nums3)
print(nums3) # Output: [1,0,0]

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
• Space Complexity: O(1). The algorithm operates in-place, using only a constant amount of extra space.