Move Zeroes - Leetcode Solution

Problem Statement:

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:

In this problem, we need to move all zeroes to the end of the array while maintaining the order of non-zero elements. We are not allowed to use extra space to solve this problem.

One approach is to use two pointers. We can initialize two pointers, i and j, both starting at index 0. We will iterate through the array with i pointer and keep j pointer pointing to the first 0 we encounter.

As we move through the array with i pointer, we check if the element at i is non-zero. If it is non-zero, we swap the elements at i and j and increment both i and j pointers to check the next element.

If we find a zero element, we simply continue to move i forward without swapping.

This approach helps us maintain the relative order of non-zero numbers while moving zeros to the end of the array.

Once we have completed traversing the array, all the zeroes will be shifted to the end of the array and all the non-zero elements will be in their original order.

Solution:

Here is the Python implementation of the above approach:

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i, j = 0, 0
        while i < n:
            if nums[i] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                j += 1
            i += 1

The time complexity of this approach is O(n) as we are only traversing the array once. The space complexity is O(1) as we are not using any extra space to solve this problem.

1