The conventional problem involving the element shifts has been discussed many times earlier, but sometimes we have strict constraints performing them and knowledge of any possible variation helps. This article talks about one such problem of shifting 0’s at end of list, catch here is it checks for just 0’s excluding the conventional ‘None’ (False) values. Let’s discuss certain ways in which this can be performed.
Method #1 : Using list comprehension + isinstance() In this method, we perform the operation of shifting in 2 steps. In 1st step we get all the values that we need to get at front and at end we just push the zeroes to end. The isinstance method is used to filter out the Boolean False entity.
Python3
# Python3 code to demonstrate# Shift zeroes at end of list# using list comprehension + isinstance()# initializing listtest_list = [1, 4, None, "Manjeet", False, 0, False, 0, "Nikhil"]# printing original listprint("The original list : " + str(test_list))# using list comprehension + isinstance()# Shift zeroes at end of listtemp = [ele for ele in test_list if ele or ele is None or isinstance(ele, bool)]res = temp + [0] * (len(test_list) - len(temp))# print resultprint("The list after shifting 0's to end : " + str(res)) |
The original list : [1, 4, None, ‘Manjeet’, False, 0, False, 0, ‘Nikhil’] The list after shifting 0’s to end : [1, 4, None, ‘Manjeet’, False, False, ‘Nikhil’, 0, 0]
Time Complexity: O(n) where n is the length of the list, since we are iterating through the list once.
Space Complexity: O(n), since we are using a list comprehension which creates a new list, and storing zeroes separately in a separate list, which results in O(n) extra space.
Method #2 : Using list comprehension + isinstance() + list slicing This method is similar to the above method, the only modification is that to reduce number of steps, list slicing is used to attach the 0’s to perform whole task in just 1 step.
Python3
# Python3 code to demonstrate# Shift zeroes at end of list# using list comprehension + isinstance() + list slicing# initializing listtest_list = [1, 4, None, "Manjeet", False, 0, False, 0, "Nikhil"]# printing original listprint("The original list : " + str(test_list))# using list comprehension + isinstance() + list slicing# Shift zeroes at end of listres = ([ele for ele in test_list if not isinstance(ele, int) or ele or isinstance(ele, bool)] + [0] * len(test_list))[:len(test_list)]# print resultprint("The list after shifting 0's to end : " + str(res)) |
The original list : [1, 4, None, ‘Manjeet’, False, 0, False, 0, ‘Nikhil’] The list after shifting 0’s to end : [1, 4, None, ‘Manjeet’, False, False, ‘Nikhil’, 0, 0]
Time complexity: O(n), where n is the length of the list. The code traverses the list once and performs operations of checking type, concatenating and slicing, which are all O(1) operations. Hence the overall time complexity is O(n).
Space complexity: O(n), where n is the length of the list. The code creates two new lists, temp and res, that take up a space proportional to the length of the original list.
Method #3 : Using counting 0’s and appending at end
- Initialize an empty list called result and a counter count to keep track of the number of zeroes encountered in the list.
- Iterate over the elements in the list. If an element is not zero, append it to the result list. If it is zero, increment the count by 1.
- Append [0] * count to the end of the result list. This will add count number of zeroes to the end of the list.
The resulting list will have all the non-zero elements from the original list followed by the zeroes that were originally scattered throughout the list.
Python3
# initializing listtest_list = [1, 4, None, "Manjeet", False, 0, False, 0, "Nikhil"]# printing original listprint("The original list : " + str(test_list))# Shift zeroes at end of listresult = []count = 0for ele in test_list: if ele == 0: count += 1 else: result.append(ele)result += [0] * count# print resultprint("The list after shifting 0's to end : " + str(result))#This code is contributed by Edula Vinay Kumar Reddy |
The original list : [1, 4, None, 'Manjeet', False, 0, False, 0, 'Nikhil'] The list after shifting 0's to end : [1, 4, None, 'Manjeet', 'Nikhil', 0, 0, 0, 0]
This approach has a time complexity of O(n), where n is the number of elements in the list, because it requires one iteration over the elements in the list. The space complexity is also O(n), because a new list with size equal to the number of elements in the original list is created.
Method #4: Using two pointers
Algorithm:
Initialize two pointers, one at the beginning (left) and the other at the end (right) of the list.
Iterate until left pointer is less than or equal to right pointer.
If the value at the left pointer is zero, swap it with the value at the right pointer and decrement the right pointer.
If the value at the left pointer is not zero, increment the left pointer.
When the iteration is complete, return the modified list.
Python3
# initializing listtest_list = [1, 4, None, "Manjeet", False, 0, False, 0, "Nikhil"]# printing original listprint("The original list : " + str(test_list))# Shift zeroes at end of list using two pointersleft, right = 0, len(test_list)-1while left <= right: if test_list[left] == 0: test_list[left], test_list[right] = test_list[right], test_list[left] right -= 1 else: left += 1# print resultprint("The list after shifting 0's to end : " + str(test_list)) |
The original list : [1, 4, None, 'Manjeet', False, 0, False, 0, 'Nikhil'] The list after shifting 0's to end : [1, 4, None, 'Manjeet', 'Nikhil', False, 0, 0, False]
Time complexity: O(n), where n is the length of the list.
Auxiliary space: O(1), as we are modifying the original list in place.
Using numpy:
Algorithm:
Convert the input list to a numpy array.
Use numpy’s boolean indexing to get a boolean array where True corresponds to non-zero elements and False corresponds to zero elements.
Use numpy’s concatenate function to concatenate two arrays:
The first array is arr[bool_arr], which selects all non-zero elements from the input list.
The second array is np.zeros(len(arr) – sum(bool_arr), dtype=int), which is a numpy array of zeroes of the same length as the number of zero elements in the input list. This ensures that all zeroes are shifted to the end of the list.
Convert the resulting numpy array to a list and return.
Python3
import numpy as npdef shift_zeroes(test_list): # converting list to numpy array arr = np.array(test_list) # getting boolean array of where elements are not 0 bool_arr = arr != 0 # getting final array with zeroes at end res = np.concatenate((arr[bool_arr], np.zeros(len(arr) - sum(bool_arr), dtype=int))) return res.tolist()# example usagetest_list = [1, 4, None, "Manjeet", False, 0, False, 0, "Nikhil"]print("The original list : ", test_list)print("The list after shifting 0's to end : ", shift_zeroes(test_list)) |
Output:
The original list : [1, 4, None, ‘Manjeet’, False, 0, False, 0, ‘Nikhil’]
The list after shifting 0’s to end : [1, 4, None, ‘Manjeet’, False, False, ‘Nikhil’, 0, 0]
Time complexity: O(n), where n is the length of the input list. The code involves creating a numpy array, doing boolean indexing, and concatenating arrays, all of which have O(n) time complexity.
Auxiliary Space: O(n), where n is the length of the input list. The numpy array and the resulting array both have O(n) space complexity.
