Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input:[0,1,0,3,12]Output:[1,3,12,0,0]
Note:
Description taken from https://leetcode.com/problems/move-zeroes/.
#O(N) Time, O(1) Spaceclass Solution: def moveZeroes(self, nums: List[int]) -> None: left = right = 0 while right < len(nums): if nums[right] != 0: nums[left], nums[right] = nums[right], nums[left] left += 1 right += 1 return numsTo solve this problem. It'd be possible to create two new lists of non-zeros and zeros then merge them at the end keeping their order. That'd require O(N) space, however.
We can instead solve this problem using two pointers. A clue for doing this is when the problem description wants us to reorder the list in a specific way, moving a specific element to one side, reversing, etc. If the order of the non-zero values did not matter, we could have a left pointer and a right pointer at both ends of the array, then move them inward swapping right zeros with left non-zeros.
Since the order does matter, however, we will use two pointers initialized at zero and traverse the array from left to right.
The left pointer will act as an anchor to store non-zeros, the right pointer will act as an anchor to store zeros.
left = right = 0 while right < len(nums):
If the value at the right pointer is a non-zero value, we will swap it with the value at the left pointer, then move the left pointer to the right. This is like us placing a bookmark at the left pointer to know where we should put any non-zero numbers when we find them.
if nums[right] != 0: nums[left], nums[right] = nums[right], nums[left] left += 1
At the end of each iteration, we will increment the right pointer and continue looking for non-zeros that we can swap to the left.
right += 1
We will return the array once all of the zeros have been moved.
return nums
The whole idea behind this two-pointer approach is we only want to move the left pointer if we have swapped its element with the right pointer's non-zero element.
We can imagine these pointers being two employees working on a marquee at a movie theatre.
The first person will stand on the left side of the marquee and wait for the second person to walk over to a plastic zero. Once the second person finds it, the first person will take off the plastic number that they are in front of and both people will toss their numbers to each other. Once this happens, the first person will take a step to the right and wait until the second person finds another non-zero number. This will continue until they have moved all of the zeros over on the marquee.