283. Move Zeroes - Explanation

Description

You are 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,0,1,2,0,5]

Output: [1,2,5,0,0,0]

Example 2:

Input: nums = [0,1,0]

Output: [1,0,0]

Constraints:

1 <= nums.length <= 10,000
-(2^31) <= nums[i] <= ((2^31)-1)

Follow up: Could you minimize the total number of operations done?

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Extra Space

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        tmp = []
        for num in nums:
            if num != 0:
                tmp.append(num)

        for i in range(len(nums)):
            if i < len(tmp):
                nums[i] = tmp[i]
            else:
                nums[i] = 0

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Two Pointers (Two Pass)

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l = 0
        for r in range(len(nums)):
            if nums[r] != 0:
                nums[l] = nums[r]
                l += 1

        while l < len(nums):
            nums[l] = 0
            l += 1

Time & Space Complexity

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

3. Two Pointers (One Pass)

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

Time & Space Complexity

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