Move Zeroes

This is an elegant problem from LeetCode (Problem #283)

Problem: 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.

Example 1:

Input: nums = [0,1,0,3,12]

Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]

Output: [0]

Solution

Once all the zeroes are moved to the end of the list, all the non-zero integers of the original list will be on the left of the list in the same order in which they appeared initially.

We use two pointers, left and right in the following way: The left pointer will point to the index where the next non-zero element needs to be placed, and the right pointer will be iterating through the list, starting from index 0.

    def moveZeroes(nums):
        left = 0        # Points to the index where the next non-zero element will go
        right = 0       # Iterates through the list
        while right < len(nums):
            if nums[right] != 0:
                nums[right], nums[left] = nums[left], nums[right]
                left += 1
            right += 1

The above algorithm can be easily understood with a simple example shown below.

Let nums = [2, 0, 7, 1]. Initially the left (L) and the right (R) pointers are both at index 0.

The pointer L points to the index where the next non-zero element to be placed.

The pointer R iterates through the list from start to end (i.e: from 0 to len(nums)-1).

Since nums[right] = nums[0] $=2\neq0$, we swap nums[left] and nums[right] (of course, they are the same elements) and increment left and right to 1.

Now nums[right] = nums[1] = 0, so we will not increment the left pointer, but will increment the right pointer. The left (L) and the right (R) pointers are therefore as shown below (i.e: left = 1, right = 2.

Now nums[right] = nums[2] = 7 $\neq 0$, so we will swap nums[right] and nums[left] and increment both pointers. So, left = 2 and right = 3.

Now nums[right] = nums[3] = 1 $\neq 0$, so we will swap nums[right] and nums[left] and increment both pointers. So, left = 3 and right = 4.

Since right = 4 = len(nums), the while loop stops, and we see that all the zeroes (there is only one in this example) have been moved to the end of the list, while the order of all the non-zero integers has been preserved.

Runtime: The total number of iterations within the while loop is $n$, and the time complexity is $O(n)$. Since the solution is generated in-place, we are not using any additional storage, so the space complexity is $O(1)$.

Back to Two Pointers Problems

---

anusha-murali.github.io