Leetcode – Duplicate Zeros Solution

Spread the love

The Duplicate Zeros problem is a common coding interview problem that can be solved using various approaches. It’s a problem that tests your understanding of array manipulation and your ability to come up with a performant solution. In this article, we’ll dive deep into the problem, understand its requirements, explore multiple ways to solve it, and analyze the time and space complexities of each solution.

Problem Description

Here’s the problem statement from LeetCode:

Given a fixed-length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written.

Do the above modifications to the input array in place, do not return anything from your function.

Example:

Input: [1,0,2,3,0,4,5,0]
Output: null (In-place operation. Array becomes [1,0,0,2,3,0,0,4])

Brute-Force Approach

One straightforward way to solve this problem is by iterating through the array and duplicating zeros while shifting elements to the right. We can achieve this using nested loops. Let’s take a look at this approach in Python:

def duplicateZeros(arr):
    i = 0
    n = len(arr)
    while i < n:
        if arr[i] == 0:
            for j in range(n-1, i, -1):
                arr[j] = arr[j-1]
            i += 2
        else:
            i += 1

Time Complexity:

The time complexity for this solution is O(n^2) because we are iterating through the array and shifting elements every time we encounter a zero.

Space Complexity:

The space complexity for this solution is O(1) as we are manipulating the array in-place without using extra memory.

Optimized Approach Using Two-Pass

We can improve the above solution by using two passes through the array. In the first pass, we can count the number of zeros that need to be duplicated. With that information, we can then start from the end of the array and copy elements to their new positions.

Here’s how we can implement this approach in Python:

def duplicateZeros(arr):
    count_zeros = arr.count(0)
    n = len(arr)
    i = n - 1
    
    while count_zeros > 0:
        if arr[i] == 0:
            if i + count_zeros < n:
                arr[i + count_zeros] = 0
            count_zeros -= 1
        
        if i + count_zeros < n:
            arr[i + count_zeros] = arr[i]
        
        i -= 1

Time Complexity:

The time complexity is O(n) for counting zeros and O(n) for the second pass, making the overall time complexity O(n).

Space Complexity:

The space complexity remains O(1) as we are doing all operations in-place.

Optimized Approach Using Queue

Another way to approach this problem is by using a queue data structure to keep track of the elements that should be moved.

Here’s how:

from collections import deque

def duplicateZeros(arr):
    n = len(arr)
    queue = deque()
    
    for i in range(n):
        queue.append(arr[i])
        
        if len(queue) > 1:
            arr[i] = queue.popleft()
        
        if arr[i] == 0 and i < n - 1:
            queue.append(0)
            i += 1
            if len(queue) > 1:
                arr[i] = queue.popleft()

Time Complexity:

The time complexity is O(n) for iterating through the array.

Space Complexity:

The space complexity is O(n) for storing the queue.

Conclusion

The Duplicate Zeros problem provides a good test for understanding array manipulations and in-place operations. While the brute-force approach has a time complexity of O(n^2), we can optimize it to O(n) time complexity with two-pass or queue methods.

Choosing the right approach depends on various factors like the constraints of the problem and the allowable space complexity. If you can’t use additional space, the two-pass method is preferable due to its O(1) space complexity. Otherwise, you may opt for the queue-based solution for its easier implementation.

Leave a Reply