Move All Zeroes to End #

Problem #

Given an array. Move all the zeroes in the array to the right end while maintaining the relative order of the non-zero elements. The operation must be performed in place.

Examples #

  • [1, 2, 0, 4, 3, 0, 5, 0] ➜ [1, 2, 4, 3, 5, 0, 0, 0]

    • There are three 0s that are moved to the end.

  • [0, 0, 0, 3, 1, 4] ➜ [3, 1, 4, 0, 0, 0]

    • There are three 0s that are moved to the end.

  • [10, 20, 30] ➜ [10, 20, 30]

    • No change in array as there are no 0s.

  • [0, 0] ➜ [0, 0]

    • No change in array as there are all 0s.

Constraints #

  • 1 ≤ arr.size() ≤ 10⁵

  • 0 ≤ arr[i] ≤ 10⁵

Expected Complexities #

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

  • Auxiliary Space: O(1)O(1)

Solution #

Python
Numeric = int | float


def move_all_zeroes_to_end(arr: list[Numeric]) -> list[Numeric]:
    zero_index: int = 0

    for i in range(len(arr)):
        if arr[i] != 0:
            # Avoid self-swapping
            if i != zero_index:
                arr[i], arr[zero_index] = arr[zero_index], arr[i]

            zero_index += 1

    return arr


print(move_all_zeroes_to_end([1, 2, 0, 4, 3, 0, 5, 0]))
print(move_all_zeroes_to_end([0, 0, 0, 3, 1, 4]))
print(move_all_zeroes_to_end([10, 20, 30]))
print(move_all_zeroes_to_end([0, 0]))