Given an array of random numbers, Push all the zeros of a given array to the end of the array. For example, if the given arrays is {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0}, it should be changed to {1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0}. The order of all other elements should be same. Expected time complexity is O(n) and extra space is O(1). Examples:
Input : arr = [1, 2, 0, 4, 3, 0, 5, 0] Output : arr = [1, 2, 4, 3, 5, 0, 0, 0] Input : arr = [1, 2, 0, 0, 0, 3, 6] Output : arr = [1, 2, 3, 6, 0, 0, 0]
We have existing solution for this problem please refer Move all zeroes to end of array link. We will solve this problem in python using List Comprehension in a single line of code.
Implementation:
Python
# Function to append all zeros at the end# of arraydef moveZeros(arr): # first expression returns a list of # all non zero elements in arr in the # same order they were inserted into arr # second expression returns a list of # zeros present in arr return [nonZero for nonZero in arr if nonZero!=0] + \ [Zero for Zero in arr if Zero==0]# Driver functionif __name__ == "__main__": arr = [1, 2, 0, 4, 3, 0, 5, 0] print (moveZeros(arr)) |
[1, 2, 4, 3, 5, 0, 0, 0]
This article is contributed by Shashank Mishra (Gullu). If you like Lazyroar and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the Lazyroar main page and help other Geeks.
Approach#2: Using while loop
This approach moves all zeroes in an input array to the end of the array while keeping the non-zero elements in their original order. It uses two pointers to keep track of the positions of the zeroes and non-zeroes in the array, and swaps them as necessary.
Algorithm
1. Initialize two pointers i and j to 0.
2. Traverse the array with j and for each non-zero element, swap arr[i] and arr[j] and increment i.
3. Return the resulting array.
Python3
def move_zeroes(arr): i, j = 0, 0 while j < len(arr): if arr[j] != 0: arr[i], arr[j] = arr[j], arr[i] i += 1 j += 1 return arrarr=[1, 2, 0, 4, 3, 0, 5, 0]print(move_zeroes(arr)) |
[1, 2, 4, 3, 5, 0, 0, 0]
Time Complexity: O(n)
Auxiliary Space: O(1)
