283. Move Zeroes
On This Page
The problem is asking to move all zeros in an integer array to the end of the array while maintaining the relative order of the non-zero elements. You must do this in-place without making a copy of the array.
A naive solution could be to create a new list, iterate over the array, add non-zero elements to the new list and count zero elements. Then extend the new list with the same amount of zeros as counted. But this solution requires creating a new list, which contradicts the in-place requirement of the problem.
Hints & Tips
The key to solve this problem is to keep a pointer, let’s call it
i, that would track the position where the next non-zero element should be placed.
The provided solution employs a two-pass approach. In the first pass, it iterates over the list and whenever it encounters a non-zero element, it places it at the position
i and increments
i. After this pass, all non-zero elements are at the beginning of the list and
i is set to the position of the first zero element.
In the second pass, it simply assigns zero to all positions from
i to the end of the list.
- Iterate over
nums. For each element, if it is not zero, assign it to
- After the iteration,
iis at the position of the first zero in
nums. Now assign zero to
i. Repeat this step until
ireaches the end of
class Solution: def moveZeroes(self, nums: List[int]) -> None: i = 0 for x in nums: # Set the non-zero elements if x != 0: nums[i] = x i += 1 while i <= len(nums) - 1: # Set the rest number of zeros nums[i] = 0 i += 1
The solution maintains the relative order of the non-zero elements and minimizes the total number of operations by only doing a single pass through the non-zero elements and then assigning zeros in one go.