Two Pointers: Move Zeroes

You are given an array of integers. You need to move all the zeroes to the end of the array while maintaining the relative order of the non-zero elements.

Write a function moveZeroes to solve this problem. The function should take in an array of integers and modify the array in-place.

Example

Input:

[0, 1, 0, 3, 12]

Output:

[1, 3, 12, 0, 0]

Approach

We can solve this problem using the Two Pointers technique. We will maintain two pointers, left and right.

1. Initialize left to 0 and right to 0.
2. Iterate through the array with the right pointer.
3. If the value at the right pointer is non-zero:
   • Swap the values at left and right pointers.
   • Increment both left and right pointers.
4. If the value at the right pointer is zero, simply increment the right pointer.
5. Repeat steps 3 and 4 until the right pointer reaches the end of the array.
6. All the non-zero elements will be moved to the left, and the zeroes will be pushed to the end of the array.

Complexity Analysis

The time complexity for this approach is O(n), where n is the length of the input array. We have to iterate through the array once to move the zeroes.

The space complexity is O(1) as we are modifying the input array in-place.

Pseudocode

def moveZeroes(nums):
    left = 0
    right = 0
    
    while right < len(nums):
        if nums[right] != 0:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
        right += 1

Implementation

Here is the implementation of the moveZeroes function in Python:

def moveZeroes(nums):
    left = 0
    right = 0
    
    while right < len(nums):
        if nums[right] != 0:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
        right += 1

Test

Let's test the function implementation using the example given in the question:

nums = [0, 1, 0, 3, 12]
moveZeroes(nums)
print(nums)  # Output: [1, 3, 12, 0, 0]

The output matches the expected result, so the function seems to be working correctly.