LeetCode 283: Move Zeroes

Description

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.

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

Constraints

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

Examples

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

Solution 1: Brute-Force

Steps

1. Iterate through the entire array starting from the last element of nums:
   1. If the current element is not 0, skip this iteration.
   2. If not, shift the entire right substring one position to the left and add a 0 at the end.

Codes

def move_zeros(nums: List[int]) -> None:
    for i in range(len(nums) - 1, -1, -1):
        if nums[i] != 0:
            continue
        else:
            for j in range(i, len(nums) - 1):
                nums[j] = nums[j + 1]
            nums[len(nums) - 1] = 0

Complexities

• Time Complexity: O(N2), where N is the length of the nums array.
• Space Complexity: O(1)

Solution 2: Two Pointers

Thought

During the iteration of nums, if we can continuously track the position where each non-zero element should be inserted, we can use a two-pointer approach to insert non-zero elements in their corresponding positions in a single pass.

Steps

1. Use two pointers, i and j, to iterate through the entire nums array. The i pointer represents the position where non-zero elements will be inserted, and the j pointer is used to find the next non-zero element. Both pointers start at the position 0.
2. Continue moving the j pointer until the end of the nums array, and during the traversal:
   1. If the current element at the j pointer is 0, continue moving the j pointer.
   2. If the current element at the j pointer is non-zero, move the current element to the position of the i pointer and simultaneously move both the i and j pointers.
3. When the j pointer reaches the end of nums, since we have moved all non-zero elements to the left side of nums, you can now replace all elements from the current position of the i pointer to the end of nums with 0‘s.

Codes

def move_zeros(nums: List[int]) -> None:
    i, j = 0, 0

    while i <= j:
        if i == len(nums):
            break
        elif j == len(nums):
            nums[i] = 0
            i += 1
        elif nums[j] != 0:
            nums[i] = nums[j]
            i += 1
            j += 1
        else:
            j += 1

Complexities

• Time Complexity: O(N), where N is the length of the nums array.
• Space Complexity: O(1)

Solution 3: Iteration and Counting

Thought

From the example, we can observe that after the entire movement of nums, each non-zero element moves a certain distance to the left, which is exactly the total count of zeros encountered up to the current element. Therefore, we can use this characteristic to continuously calculate the total count of zeros encountered during traversal and move each non-zero element to its corresponding position.

Steps

1. Initialize a variable zero_count to keep track of the total count of zeros encountered so far in the traversal.
2. First iteration:
   1. If you encounter a 0, increment zero_count by 1.
   2. If you encounter a non-zero element, move the current element zero_count positions to the left.
3. Second iteration:
   1. Replace all elements from len(nums) - zero_count to the end of the nums array with 0‘s.

Codes

def move_zeroes(nums: List[int]) -> None:
    zero_count = 0
    for i, num in enumerate(nums):
        if num == 0:
            zero_count += 1
        else:
            nums[i - zero_count] = num

    for i in range(len(nums) - zero_count, len(nums)):
        nums[i] = 0

Complexities

• Time Complexity: O(N), where N is the length of the nums array.
• Space Complexity: O(1)

References

• LeetCode link: Move Zeroes – LeetCode