DEV Community

Cover image for LeetCode Challenge: Move Zeroes
Bharath Sriraam R R
Bharath Sriraam R R

Posted on • Edited on

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

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay