Problem¶

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.

Constraints:

1 <= nums.length <= 10**4
-2**31 <= nums[i] <= 2**31 - 1

Example 1:

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

Solve¶

Bubble Sort¶

-2**31 <= nums[i] <= 2**31 - 1 so we not want to count that much, even of you want to, consider using a dict() hash map
Quite simple problem, but they want you to keeping nums in-place which causing some trouble as we dealing with python array (Which is way more than just a normal array)

Here i using bubble sort to push all 0 number to the end, which is a O(n**2) time complexity function

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        for i in range(len(nums)):
            for j in range(len(nums)-i-1):
                if nums[j] == 0:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
        return nums

void moveZeroes(int* nums, int numsSize){
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < numsSize - i - 1; j++) {
            if (nums[j] == 0) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

Just sort it¶

Change all number 0 value to max number, sort it, using temp array to store processing data, update the nums array to match with processed result.

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        key = [len(nums)+1] * len(nums)
        index = 0
        for i, v in enumerate(nums):
            if v != 0:
                key[index] = i
                index += 1

        key.sort()
        tmp = [0] * len(nums)

        for i, k in enumerate(key):
            if k >= len(nums):
                break
            tmp[i] = nums[k]

        for i, v in enumerate(tmp):
            nums[i] = v

Not even sorting¶

Create a temp table. Loop through all available number and if it not 0 push to tmp array one by one

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        tmp = [0] * len(nums)
        index = 0
        for v in nums:
            if v != 0:
                tmp[index] = v
                index += 1

        for i, v in enumerate(tmp):
            nums[i] = v

Last update : October 13, 2023
Created : August 16, 2023