How would you move all zeros in an array to the end?

Moving all zeros in an array to the end can be achieved through an algorithmic technique called "two-pointer technique". Following the steps below will accomplish this:

1. Initialize two pointers ‘i‘ and ‘j‘ to 0.

2. Run a while-loop until ‘i‘ reaches the end of the array.

3. If the array[i] is non-zero, swap the array[i] and array[j] and increment both ‘i‘ and ‘j‘.

4. If the array[i] is 0, increment ‘i‘ only.

Here’s corresponding Python code and explanation:

def move_zeros_to_end(arr):
    n = len(arr)

    j = 0  # Count of non-zero elements
    for i in range(n):
        # If element at index i is non-zero, then replace the element
        # at index j with this element
        if arr[i] != 0:
            # Swap
            arr[j], arr[i] = arr[i], arr[j]
            # increment count of non-zero elements
            j += 1

    return arr

You could call the function with your array, like so:

arr = [1, 0, 2, 0, 3, 0, 0, 4, 5]
print(move_zeros_to_end(arr))

This would result in:

Output: [1, 2, 3, 4, 5, 0, 0, 0, 0]

The time complexity of the above algorithm is O(n) because the array is traversed once only. The space complexity is O(1), no extra space is used. Plus, this is an in-place algorithm which means original order of non-zero elements is maintained.

Here’s a step-by-step illustration of how the algorithm works for the following input: [1, 0, 2, 0, 3, 0, 0, 4, 5] i and j both start at index 0.

arr: [1, 0, 2, 0, 3, 0, 0, 4, 5]
         i
         j

Since ‘arr[i]‘ is not zero, ‘arr[j]‘ and ‘arr[i]‘ are swapped and both ‘i‘ and ‘j‘ are incremented. Now our array and pointers both look like this:

arr: [1, 0, 2, 0, 3, 0, 0, 4, 5]
             i
             j

Since ‘arr[i]‘ is zero, only the ‘i‘ pointer will be incremented and thus the following state:

arr: [1, 0, 2, 0, 3, 0, 0, 4, 5]
                 i
             j

The process continues similarly, with ‘i‘ and ‘j‘ pointers incrementing under different conditions until ‘i‘ reaches the end of the array, with final result of ‘[1, 2, 3, 4, 5, 0, 0, 0, 0]‘.