Move all zeros to the end of an array.
Easy
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:
Time 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).
Interview experiences
2 sharedRelated questions
Given an array of integers, print all subarrays that sum to zero.Related courses
