algoadvance

LeetCode Problem 283: Move Zeroes

Given an integer array nums, move all 0s to the end of it while maintaining the relative order of the non-zero elements.

Clarifying Questions

1. Input Size:
   • What is the size range of the input array?
2. Element Size:
   • Can the array contain negative numbers, or is it only non-negative numbers?
3. In-Place Requirement:
   • Should the operation be performed in place?
4. Return Value:
   • Is the function supposed to return the modified array or should it modify the array in place without returning it?

Code

def moveZeroes(nums):
    """
    Move all 0's to the end of the array while maintaining the relative order of non-zero elements.
    
    Args:
    nums (List[int]): List of integers.
    
    Returns:
    None: The function modifies the input list in place.
    """
    # Initialize the index for the place to move the next non-zero number
    last_non_zero_found_at = 0

    # First pass: move all non-zero elements to the 'last_non_zero_found_at' index
    for current in range(len(nums)):
        if nums[current] != 0:
            nums[last_non_zero_found_at] = nums[current]
            last_non_zero_found_at += 1

    # Second pass: fill the remaining positions with zeroes
    for current in range(last_non_zero_found_at, len(nums)):
        nums[current] = 0

Strategy

1. Initial Setup:
   • We first initialize the last_non_zero_found_at index to 0. This will keep track of the position to place the next non-zero number.
2. First Pass (Move Non-Zeroes):
   • We iterate through the array using an index current.
   • For every non-zero element encountered, we place it at the last_non_zero_found_at position and then increment last_non_zero_found_at.
3. Second Pass (Fill Zeroes):
   • After placing all non-zero elements correctly, last_non_zero_found_at will be the index of the first position to fill with 0.
   • We fill all remaining positions with 0 from last_non_zero_found_at to the end of the array.

Time Complexity

• First Pass: O(n), where n is the number of elements in the array. We traverse the array once to move non-zero elements to the front.
• Second Pass: O(n), where n is the number of elements in the array. We traverse the array again to fill the remaining positions with zeros.
• Overall: O(n), as both passes involve traversing the array linearly.

This solution efficiently uses the in-place replacement strategy, ensuring minimal space usage and maintaining optimal time complexity.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?