Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
LeetCode Solutions1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1Could you minimize the total number of operations done?
In the worst case, for each zero element, we may have to scan the remaining array to find a non-zero element.
We are modifying the array in-place and not using any extra space.
The brute force approach iterates through the array and whenever it encounters a zero, it looks for the next non-zero element and swaps it with the current zero element. This process continues until all zeros are moved to the end of the array.
We iterate through the array once, and each swap operation takes constant time.
We are modifying the array in-place and not using any extra space.
The two-pointer approach uses two pointers, left and right. The right pointer iterates through the array, while the left pointer keeps track of the position where the next non-zero element should be placed. Whenever a non-zero element is found at the right pointer, it is swapped with the element at the left pointer, and the left pointer is incremented. This way, all non-zero elements are moved to the front of the array, and all zeros are moved to the end.
| Approach | Rating | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|---|
| Brute Force | Simple to understand | ⚠️ Inefficient — nested loops for each zero | |||
| Two Pointers | Optimal time and space, maintains relative order, single pass | None |
The optimal approach for this problem is Solution 2: Two Pointers, which achieves time complexity and space complexity. It uses a left pointer to track where the next non-zero element should be placed, and a right pointer to scan through the array, swapping non-zero elements into position in a single pass.
class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ for i in range(len(nums)): if nums[i] == 0: # Find the next non-zero element and swap it with the current zero element for j in range(i, len(nums)): if nums[j] != 0: temp = nums[j] nums[j] = nums[i] nums[i] = temp breakclass Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ left = 0
for right in range(len(nums)): # If the current element is not zero, swap it with the element at the left pointer if nums[right] != 0: nums[left], nums[right] = nums[right], nums[left]
left += 1