283_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.

Note:

  1. You must do this in-place without making a copy of the array.

  2. Minimize the total number of operations.

Example

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

Solution

Idea:

  • Use two pointers. Slow pointer indicates first zero location, fast pointer indicates first non-zero location.

  • Loop the fast pointer, and record the first available zero element in the array as the slow pointer. Swap the elements in the fast pointer and slow pointer when they are not the same.

  • All elements between the slow and faster pointer are zeroes.

Time Complexity: O(n)O(n)

Space Complexity: O(1)O(1)

def moveZeroes(self, nums):
    """
    :type nums: List[int]
    :rtype: void Do not return anything, modify nums in-place instead.
    """
    # slower pointer
    j = 0

    # faster pointer
    for i in range(len(nums)) :
        if nums[i] != 0 :
            if i != j:
                nums[i], nums[j] = nums[j], nums[i]
            j += 1

Last updated