Given an array of integers, move zeros to the end while keeping the order of the rest.
You should make the in-place change.
Example
const list = [1,0,0,2,3]
moveZeros(list)
console.log(list) // [1,2,3,0,0]
Notes: What is the time & space complexity of your approach?
Solution 1
function moveZeros(arr) {
let i = 0,
j = arr.length - 1;
while (i < j) {
while (arr[j] === 0 && i < j) j--;
if (arr[i] === 0) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
i++;
}
}
Explanation
It uses two pointers, i and j, to track the current element and the next non-zero element. The loop iterates until i and j meet. Inside the loop, the code first checks if the element at index j is equal to 0. If it is, then the code decrements j. Otherwise, the code checks if the element at index i is equal to 0. If it is, then the code swaps the elements at indices i and j. Finally, the code increments i.
Solution 2
function moveZeros(arr) {
let i = 0,
j = 0;
while (i < arr.length) {
if (arr[i] !== 0) {
arr[j] = arr[i];
j++;
}
i++;
}
while (j < arr.length) {
arr[j] = 0;
j++;
}
}
Explanation
- The moveZeros() function takes an array as input and returns the modified array.
- The function first initializes two variables, i and j. i is used to iterate through the array, and j is used to track the index of the next non-zero element.
- The function then iterates through the array, starting at index i. If the current element is not equal to 0, then the element is swapped with the element at index j. The value of j is then incremented.
- After the loop has finished, the remaining elements in the array are all zeros.
- The function then returns the modified array.
Approach | Advantages | Disadvantages |
---|---|---|
First approach | Only traverses the array once. Easy to understand and maintain. |
Not as space-efficient as the second approach. |
Second approach | Space-efficient. Easy to understand and maintain. |
* Traverses the array twice. |
Top comments (0)