Practice: Move Zeros to End of Array
Move all zeros to the end of an array while maintaining the order of the other elements. Given an array of integers, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Constraints
- You must do this in-place without making a copy of the array.
- Minimize the total number of operations.
For example, given the input array [0, 1, 0, 3, 12], after calling your function, the array should be [1, 3, 12, 0, 0].
Examples
arr = [0, 1, 0, 3, 12] output: [1, 3, 12, 0, 0] arr = [1, 2, 0, 4, 3, 0, 5, 0] output: [1, 2, 4, 3, 5, 0, 0, 0] arr = [1] output: [1] arr = [0, 0, 1] output: [1, 0, 0]
Let arr be an array of length n.
The goal of the moveZerosToEnd function is to move all zeros in the array to the end while maintaining the relative order of the non-zero elements. Here's how we can achieve this:
- Calculate the Length: Determine the length of the input array.
- Handle Short Arrays: If the array length is less than 2, return the array as it is, since there are no zeros to move.
- Initialize a Counter: Create a variable
counterset to 0. This will keep track of the next position to place a non-zero element. - Iterate Through the Array: Loop through each element of the array using
enumerateto get both the index and the value.- If the current element is not zero, place it at the position indicated by
counterand incrementcounter.
- If the current element is not zero, place it at the position indicated by
- Fill with Zeros: After all non-zero elements have been moved to the front, fill the remaining positions in the array with zeros.
- Return the Modified Array: The array is now transformed such that all non-zero elements are at the beginning, followed by all the zeros.
Here is the function implementation:
def moveZerosToEnd(arr):
# Calculate the length of the input array
length = len(arr)
# If the length of the array is less than 2, there's no need to perform any operations,
# so we return the array as is
if length < 2:
return arr
# Initialize a variable 'counter' to keep track of the current position where we will insert non-zero elements
counter = 0
# Iterate through each element of the array using enumerate, which provides both the index and the value
for idx, val in enumerate(arr):
# If the value is not zero, move it to the position indicated by 'counter' and increment 'counter' by 1
if val != 0:
arr[counter] = val
counter += 1
# After processing all non-zero elements, fill the remaining positions in the array with zeros
# by continuing to increment 'counter' until it reaches the length of the array
while counter < length:
arr[counter] = 0
counter += 1
# Return the modified array, where all non-zero elements have been moved to the beginning followed by zeros
return arrTime Complexity: The function processes each element of the array exactly once in the first loop (n). The second loop starts at the position indicated by counter and goes to the end of the array, filling in zeros (n - counter). Total time complexity is O(n + n - counter) = O(2n - counter) = O(n).
Space Complexity: The function modifies the array in place and uses a constant amount of additional space (the counter variable). Thus, the space complexity is O(1).