Problem
Given an integer array nums, move all 0s to the end while maintaining the relative order of the non-zero elements. Modify in-place.
Example
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]Solution
Two pointers. Slow tracks the next position for a non-zero. Fast scans the array.
def move_zeroes(nums):
slow = 0
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1function moveZeroes(nums) {
let slow = 0;
for (let fast = 0; fast < nums.length; fast++) {
if (nums[fast] !== 0) {
[nums[slow], nums[fast]] = [nums[fast], nums[slow]];
slow++;
}
}
}void moveZeroes(vector<int>& nums) {
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast] != 0) {
swap(nums[slow], nums[fast]);
slow++;
}
}
}public void moveZeroes(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 0) {
int temp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = temp;
slow++;
}
}
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
Each non-zero gets swapped to the slow pointer position. Zeroes naturally end up at the end. Single pass, no extra space.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?