Leetcode – Move Zeroes Solution in Python

Spread the love

In this exhaustive article, we will dive into a popular problem on LeetCode, known as the ‘Move Zeroes’. This problem is often encountered in coding interviews and serves as an excellent measure of a candidate’s understanding of arrays and algorithm optimization. We will delve into the problem statement, discuss various approaches to solving the problem, and analyze their time and space complexities.

Introduction

First, let’s take a look at the problem statement:

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. You must do this in-place without making a copy of the array, and minimize the total number of operations.

Example:

Input: [0,1,0,3,12]

Output: [1,3,12,0,0]

Understanding the Problem

In this problem, we are given an array with integers and we have to move all the zeroes to the end of the array. It’s important to note that the relative order of the non-zero elements must be maintained.

Naive Approach: Using an Auxiliary Array

A simple method to solve this problem is to use an auxiliary array. We can iterate through each element in the input array and copy the non-zero elements to the auxiliary array. After we have copied all the non-zero elements, we can fill the rest of the auxiliary array with zeroes. Finally, we can copy the auxiliary array back to the original array.

def moveZeroes(nums):
    # Create an auxiliary array
    aux = []
    
    # Copy non-zero elements to the auxiliary array
    for num in nums:
        if num != 0:
            aux.append(num)
    
    # Append zeros to the auxiliary array
    aux.extend([0] * (len(nums) - len(aux)))
    
    # Copy the auxiliary array back to the original array
    for i in range(len(nums)):
        nums[i] = aux[i]

Time Complexity:

O(n) – We iterate through the entire array once to copy non-zero elements and once again to copy them back.

Space Complexity:

O(n) – We use an auxiliary array of the same size as the input array.

This approach doesn’t fulfill the requirement of doing it in-place.

Optimal Approach: Two Pointers

We can solve this problem in-place by using two pointers. This approach will also minimize the total number of operations.

  1. Initialize two pointers, pos and i. Set both of them to the start of the array.
  2. Iterate through the array using the i pointer.
  3. Whenever nums[i] is non-zero, swap the elements nums[pos] and nums[i] and move pos to the next index.
  4. Increment i in each iteration.
def moveZeroes(nums):
    # Position to place the next non-zero element
    pos = 0
    
    # Iterate through the array
    for i in range(len(nums)):
        # If the current element is non-zero, swap it to the position
        # indicated by 'pos' and move 'pos' one step forward
        if nums[i] != 0:
            nums[i], nums[pos] = nums[pos], nums[i]
            pos += 1

Time Complexity:

O(n) – We go through the array once, performing constant-time operations for each element.

Space Complexity:

O(1) – This approach only uses a constant amount of additional space.

A Variant: Counting Zeroes

Another approach is to first move all the non-zero elements to the front and then fill in the zeroes. This is slightly different from the two-pointer approach.

  1. Iterate through the array and count the number of zeroes.
  2. Iterate again and for each non-zero element, move it to the front. Keep track of the position where the next non-zero element should go.
  3. After all non-zero elements are at the front, fill in the zeroes at the end.
def moveZeroes(nums):
    # Count the zeroes
    num_zeroes = 0
    for num in nums:
        if num == 0:
            num_zeroes += 1
    
    # Move non-zero elements forward
    pos = 0
    for num in nums:
        if num != 0:
            nums[pos] = num
            pos += 1
    
    # Fill in the zeroes
    for i in range(num_zeroes):
        nums[pos] = 0
        pos += 1

Time Complexity:

O(n) – We have two separate loops that iterate through the array.

Space Complexity:

O(1) – This approach only uses a constant amount of additional space.

Conclusion:

The Move Zeroes problem on LeetCode is a classic example that tests a candidate’s understanding of array manipulations and optimization techniques. The two-pointer approach is an optimal solution in terms of both time and space complexity. It’s also worth noting that different variants of the two-pointer approach, like the counting zeros variant, can sometimes offer more intuitive solutions for some people. It’s crucial to practice such problems to develop a strong foundation for solving array-based coding challenges efficiently.

Leave a Reply