Move Zeroes

Clarify the problem:

• The problem requires moving all the zeros in an array to the end while maintaining the order of the non-zero elements.
• We need to implement a function that takes an array of integers as input and modifies it in-place, moving all the zeros to the end.

Analyze the problem:

• Input: An array of integers.
• Output: None (the array should be modified in-place).
• Constraints:
  • The length of the array can be in the range [0, 10^4].
  • The array may contain both positive and negative integers.

Design an algorithm:

• We can solve this problem by using the two-pointer technique.
• We will initialize two pointers, i and j, both pointing to the start of the array.
• We iterate through the array using pointer i. If the element at index i is non-zero, we swap it with the element at index j and increment j.
• After iterating through the array, all non-zero elements will be moved to the left side of the array, and the zeros will be at the end.
• Finally, we fill the remaining elements from index j to the end of the array with zeros.

Explain your approach:

• We will implement a function called moveZeroes that takes an array as input.
• We will initialize two pointers, i and j, both initially pointing to the start of the array.
• We will iterate through the array using pointer i from left to right.
• If the element at index i is non-zero, we swap it with the element at index j and increment j.
• After iterating through the array, all non-zero elements will be moved to the left side of the array, and the zeros will be at the end.
• Finally, we fill the remaining elements from index j to the end of the array with zeros.

Write clean and readable code:

python

def moveZeroes(nums):
    if nums is None:
        return

    n = len(nums)
    j = 0

    for i in range(n):
        if nums[i] != 0:
            nums[j], nums[i] = nums[i], nums[j]
            j += 1

    while j < n:
        nums[j] = 0
        j += 1

Test your code:

python

# Test case 1
nums = [0, 1, 0, 3, 12]
# After moving the zeros, the array should be [1, 3, 12, 0, 0]
moveZeroes(nums)
assert nums == [1, 3, 12, 0, 0]

# Test case 2
nums = [0, 0, 0, 0, 0]
# After moving the zeros, the array should remain the same: [0, 0, 0, 0, 0]
moveZeroes(nums)
assert nums == [0, 0, 0, 0, 0]

# Test case 3
nums = [1, 2, 3, 4, 5]
# There are no zeros in the array, so it should remain the same: [1, 2, 3, 4, 5]
moveZeroes(nums)
assert nums == [1, 2, 3, 4, 5]

# Test case 4
nums = [0, 0, 1, 0, 3, 0, 0, 12, 0, 0]
# After moving the zeros, the array should be [1, 3, 12, 0, 0, 0, 0, 0, 0, 0]
moveZeroes(nums)
assert nums == [1, 3, 12, 0, 0, 0, 0, 0, 0, 0]

Optimize if necessary:

• The provided solution has a time complexity of O(n) since we iterate through the array once.
• The space complexity is O(1) since we do the modification in-place without using any extra space.

Handle error cases:

• The given code assumes that the input nums is a valid list of integers. If the input is not a valid list or contains invalid values, it may result in unexpected behavior.

Discuss complexity analysis:

• The time complexity of the solution is O(n), where n is the length of the input array. We iterate through the array once.
• The space complexity is O(1) since we perform the modification in-place without using any extra space.