Move all zeroes to the end of the array while maintaining the relative order of the non-zero elements.
Problem Statement
Given an integer array, move all 0s to the end of it while maintaining the relative order of the non-zero elements.
Examples
Input: arr = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]
Explanation: Zeros are pushed to the end.
Constraints
Standard constraints
Complexity
Time Complexity: O(N)
Space Complexity: O(1)
Hints
š” Hint 1:
Use a two-pointer approach to keep relative order of non-zero elements.
š” Hint 2:
Maintain an insertPos pointer where the next non-zero element should go.
š” Hint 3:
Iterate through the array. When you encounter a non-zero, swap arr[i] with arr[insertPos] and advance insertPos.
Editorial & Approach
Problem Overview & Intuition
We want to shift all zeroes to the end of the array while maintaining the original relative order of non-zero elements. A single pointer tracking the next non-zero slot allows us to swap in-place in O(N) time.
Step-by-Step Approach
- Initialize
insertPos = 0. - Iterate
ifrom0toarr.length - 1. - Whenever
arr[i] !== 0, swaparr[insertPos]andarr[i], then incrementinsertPos++. - Return the modified
arr.
Optimal Implementation (JavaScript)
function moveZeros(arr) {
let insertPos = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== 0) {
const temp = arr[insertPos];
arr[insertPos] = arr[i];
arr[i] = temp;
insertPos++;
}
}
return arr;
}Complexity Analysis
Time Complexity
O(N) ā single traversal of the array.
Space Complexity
O(1) ā in-place swapping with no secondary array.
Edge Cases & Corner Traps Handled
- No zeroes in array: elements remain in place.
- All zeroes in array: elements remain in place.
- Single element [0]: returns [0].