LeetCode Challenge: Move Zeroes

If you've been following this series so far, then this problem should be a piece of cake.

Problem

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]

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

Approach 1

Algorithm:

1. Initialize variable zeroCount to store count of zeroes
2. Initialize result to store the final array
3. Iterate through all elements of the array
4. If the element is zero then increment zeroCount
5. Else append to the result array
6. Append zeroCount number of zeroes to the result
7. Replace elements of original array with result

Code:

def approach1(nums):
    zeroCount = 0
    result = []

    for i in range(len(nums)):
        if nums[i] == 0:
            zeroCount += 1
        else:
            result.append(nums[i])

    for i in range(zeroCount):
        result.append(0)

    for i in range(len(nums)):
        nums[i] = result[i]

    return nums

Complexity analysis:

Time complexity: O(n) Always n operations
Space complexity: O(n)

Approach 2

Algorithm:

1. Initialize variable nextIndex to store the next index of non zero element
2. Iterate through all elements of the array
3. If the current element is not zero then put it at nextIndex and increment it
4. Once step 2 ends iterate from nextIndex to the end of the array and assign zero at those indices

Code:

def approach2(nums):
    nextIndex = 0

    for i in range(len(nums)):
        if nums[i] != 0:
            nums[nextIndex] = nums[i]
            nextIndex += 1

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

    return nums

Complexity analysis:

Time complexity: O(n) with near minimum operations
Space complexity: O(1)

Approach 3

Algorithm:

1. Initialize variable nextIndex to store the next index of non zero element
2. Iterate through all elements of the array
3. If the current element is not zero then swap it with the element at nextIndex and increment it

Code:

def approach3(nums):
    nextIndex = 0

    for i in range(len(nums)):
        if nums[i] != 0:
            nums[i], nums[nextIndex] = nums[nextIndex], nums[i]
            nextIndex += 1

    return nums

Complexity analysis:

Time complexity: O(n) with minimum operations
Space complexity: O(1)

Summary

This problem was more of tricky thinking rather than algorithmic thinking.

Here's the replit