Shifiting a list

def shifting_zeros(arr):
    for elem in arr:
        if elem == 0:
            arr.remove(elem)
            arr.append(0)
    return arr



def better_function(arr):
    temp = []
    z = 0
    for elem in arr:
        if elem != 0:
            temp.append(elem)
        else:
            z = z + 1
    temp.extend(z * [0])
    return temp


import random
import time

n = 200_000
array = [random.randint(0, 9) for _ in range(n)]

start = time.time()
x = shifting_zeros(array)
stop = time.time()
print(stop-start) 
# --> around 100 sec


start = time.time()
x = better_function(array)
stop = time.time()
print(stop-start) 
# ---> below 1 sec

Shifting zeros function

The function iterates over each element in the input array. If an element is 0, it removes that element from the array (arr.remove(elem)), which is O(n) in complexity because list.remove searches for the element. Then, it appends 0 to the end of the array (arr.append(0)), which is O(1).

Time Complexity:

• The outer loop runs for all elements in arr, which is O(n).
• For each 0 in the array, the remove operation takes O(n) time. Therefore, if there are m zeros in the array, the time complexity is approximately: O(n⋅m)
• In the worst case (if the entire array consists of zeros), this becomes O(n²).

Space Complexity:

• Operates in-place, so the space complexity is O(1).

Detaild explanation

The list.remove(elem) operation in Python takes O(n) time because it involves the following steps:

1. Search for the Element:

When you call arr.remove(elem), Python first scans the list to locate the first occurrence of elem. This involves a linear search through the list, which has a worst-case complexity of O(n) where n is the length of the list.

For example, in the list [1, 2, 3, 0, 4], if you call arr.remove(0), Python must iterate over the first three elements (1, 2, and 3) before it finds the 0.

2. Shift Elements After Removal:

Once the element is found and removed, all the elements after the removed element need to be shifted one position to the left to fill the gap.

For example, if you remove the 0 from [1, 2, 0, 3, 4], the list is updated like this: [1, 2, 3, 4]

This shifting operation also takes O(n) time in the worst case, depending on how many elements follow the removed element.

“Better function” function

• Creates a new list temp to hold non-zero elements.
• Iterates through the array and appends non-zero elements to temp. Simultaneously, it counts the number of zeros (z).
• At the end, it extends temp with z zeros.

Time Complexity:

• Iterating over the array is O(n).
• Appending to temp and extending it are O(1) operations.
• Hence, the overall time complexity is O(n).

Space Complexity:

• Uses an additional list temp and allocates memory for z zeros, so the space complexity is O(n).