2022-01-31-164040-283_move_zeroes.org

283 Move Zeroes

Description

Given an integer array nums, move all 0 to the end of the it while maintaining the relative order of the non-zero elements.

Constraints:

1. You must do this in-place without making a copy of the array.
2. $1\leq nums.length \leq 10⁴$
3. $-2³¹ \leq nums[i] \leq 2³¹-1$

Examples:

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

Input: nums = [0]
Output: [0]

Solution

Understanding the problem

Again, let’s first consider the trivial case where len(nums) == 1. We don’t need to do anything in this case.

In general, we will have to at least scan nums once.

Algorithm

Scan the array and look for 0’s and record their position. Iterate through their positions and remove zeroes, append zero in the end.

Code

def moveZeroes(nums):
    """
    :type nums: List[int]
    :rtype: None Do not return anything, modify nums in-place instead.
    """
    poses = []
    for i, n in enumerate(nums):
        if n == 0:
            poses.append(i)

    for i, pos in enumerate(poses):
        # we use pos-i because we moved i number of zeros to the end
        nums.append(nums.pop(pos-i))


# tests
nums = [0]
moveZeroes(nums)
print(nums == [0])

nums = [0, 1]
moveZeroes(nums)
print(nums == [1, 0])

nums = [0, 1, 2, 0]
moveZeroes(nums)
print(nums == [1, 2, 0, 0])

nums = [1, 2 ]
moveZeroes(nums)
print(nums == [1, 2])

Complexity

Time complexity:

O(n), one full scan.

Space complexity:

O(n), potentially nums can be all zeroes so len(poses) == len(nums).

Leetcode solution

nil.

<<imports for typing>>

Time complexity:

Space complexity:

More analysis

General thoughts

Related problems

Log time