Talha Gillani

What is the problem

Let’s start from simple thought process, and then build the understanding step by step. The challenge is to move all non-zeroes to the start of the array without increasing the space complexity (e.g. by creating temporary array).

Naive Solution

We can let go of the restriction of in-place restriction in the problem to make things simple first. We can create a temporary array with space complexity of O(N) filled with zeroes of length same as given array as input. Then we can just iterate through the given input array once:

from typing import List

def move_zeroes_naive(arr: List[int]) -> List[int]:
    """
    Naive Solution:
    TC - Time Complexity: O(N)
    SC - Space Complexity: O(N)
    """
    
    arr_size = len(arr) # TC: O(N)
    temp_arr = [0] * arr_size # SC: O(N) TC: O(N)
    temp_arr_counter = 0
    
    for i in range(arr_size): # TC: O(N)
        # check for non-zero
        if arr[i] != 0:
            temp_arr[temp_arr_counter] = arr[i]
            temp_arr_counter += 1
    return temp_arr

if __name__ == "__main__":
    arr: List[int] = [0,1,0,3,12]
    print(move_zeroes_naive(arr)) # [1, 3, 12, 0, 0]

Optimized Solution

We can see that we are comparing zeroes and non-zeroes as we iterate through the sequential data structure array. A Coding Interview Pattern that comes to mind is Two-Pointer. One pointer’s responsibility would be to be on the position where non-zero values could be swapped with (e.g. indices of zero numbers in array). Other pointer’s responsibility would be iterate through the array.

from typing import List



def move_zeroes_optimized(arr: List[int]) -> None:
    """
    Optimized Solution - Two Pointer:
    TC - Time Complexity: O(N)
    SC - Space Complexity: O(1)
    """

    place = None # SC: O(1)
    for i in range(len(arr)):
        if arr[i] == 0 and place is None:
            place = i
        if arr[i] != 0 and place is not None:
            arr[i], arr[place] = arr[place], arr[i]
            place += 1
    
    print(arr)


if __name__ == "__main__":
    arr: List[int] = [0,1,0,3,12]
    move_zeroes_optimized(arr) # [1, 3, 12, 0, 0]
    

Youtube