Move Zeroes

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]

Approach:

This problem could easily be implemented by making a copy of the array therefore we'll focus on a more efficient implementation.

• We initialize two pointers i = 0, j = 0. Iterate j over range(len(nums))

• if nums[j] != 0, we swap nums[i] and nums[j], and increment i by 1.

We can now observe that the loop invariant nums[:i+1] contains all nonzero elements in nums[:j+1] with relative order preserved. Hence when j reaches len(nums)-1, nums[:i+1] contains all nonzero elements in nums with relative order preserved.

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        i = 0
        for j in range(len(nums)):
            if nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

Time: O(n) Space: O(1)