LeetCode 1089 - Duplicate Zeros

The problem asks us to modify a fixed-length integer array in-place by duplicating each zero and shifting the subsequent elements to the right.

leetcodeeasyarraytwo-pointers

LeetCode Problem 1089

Difficulty: 🟢 Easy
Topics: Array, Two Pointers

Solution

Problem Understanding

The problem asks us to modify a fixed-length integer array in-place by duplicating each zero and shifting the subsequent elements to the right. The critical part of the problem is that the array has a fixed length, so any elements that would go beyond the original size are discarded. For example, if duplicating a zero would push an element outside the array bounds, that element is simply lost.

The input array arr contains integers between 0 and 9, and its length is between 1 and 10^4. The expected output is the same array modified in-place to reflect the zero duplications. This is an in-place problem, so no new arrays should be created.

Edge cases to consider include arrays with no zeros (nothing changes), arrays filled entirely with zeros (many elements are lost), zeros at the end of the array (duplicating them may overflow), and arrays of length one (trivial but should not fail).

Approaches

A naive or brute-force approach iterates through the array from left to right, and every time it encounters a zero, it shifts all subsequent elements one position to the right to make space for the duplicated zero. This approach is correct because it literally simulates the process described in the problem, but it is inefficient. Shifting elements repeatedly results in O(n^2) time complexity, which can be very slow for arrays of length up to 10,000.

The optimal approach uses a two-pass strategy and the insight that we only need to know which elements will be visible after duplicating zeros. First, we count how many zeros will be duplicated without exceeding the array bounds. Then, we iterate backward from the end of the array, copying elements to their correct positions in reverse order. By iterating backward, we avoid overwriting elements we still need to process. This approach works in-place in O(n) time and O(1) additional space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Shift elements right for each zero, slow for large arrays
Optimal O(n) O(1) Count zeros, copy elements backward to avoid overwriting

Algorithm Walkthrough

  1. Calculate the total number of zeros that need to be duplicated. Iterate through the array from left to right, maintaining a count of zeros. If the total positions required (original length + zero count) exceed the array length, adjust the count so we only duplicate zeros that fit within the array bounds.
  2. Start iterating from the last index of the original array in reverse. Maintain a virtual index that represents the position in the expanded array (including duplicates).
  3. For each element, if it is a zero, write two zeros at the correct positions in the array if they are within bounds. For non-zero elements, copy the element to the calculated position in the array.
  4. Decrement the backward pointers and continue until the start of the array is reached.

Why it works: By iterating backward and using a virtual index to represent positions after duplication, we avoid overwriting elements that we have not yet processed. This guarantees the in-place modification is correct and all zeros are duplicated as needed.

Python Solution

from typing import List

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        n = len(arr)
        zeros_to_duplicate = 0
        for num in arr:
            if num == 0:
                zeros_to_duplicate += 1

        i = n - 1
        j = n + zeros_to_duplicate - 1

        while i >= 0:
            if j < n:
                arr[j] = arr[i]
            if arr[i] == 0:
                j -= 1
                if j < n:
                    arr[j] = 0
            i -= 1
            j -= 1

The implementation first counts the zeros to determine how many duplications can fit. Then, it iterates backward using two pointers: i for the original array and j for the "virtual" extended array. Elements are copied to their new positions. If a zero is encountered, it is duplicated, but only if the position is within the original array bounds.

Go Solution

func duplicateZeros(arr []int)  {
    n := len(arr)
    zerosToDuplicate := 0
    for _, num := range arr {
        if num == 0 {
            zerosToDuplicate++
        }
    }

    i := n - 1
    j := n + zerosToDuplicate - 1

    for i >= 0 {
        if j < n {
            arr[j] = arr[i]
        }
        if arr[i] == 0 {
            j--
            if j < n {
                arr[j] = 0
            }
        }
        i--
        j--
    }
}

The Go implementation mirrors the Python version. Go slices handle bounds checks, so we explicitly check j < n before writing. The backward iteration and virtual index logic remain identical.

Worked Examples

Example 1: [1,0,2,3,0,4,5,0]

Step i j arr state
Initial 7 10 [1,0,2,3,0,4,5,0]
i=7 (0) 6 9 [1,0,2,3,0,4,5,0]
write zero 6 8 [1,0,2,3,0,4,5,0]
i=6 (5) 5 7 [1,0,2,3,0,4,5,0]
write 5 5 6 [1,0,2,3,0,4,5,0]
continue backward ... ... ...

Final array: [1,0,0,2,3,0,0,4]

Example 2: [1,2,3]

No zeros to duplicate. Array remains [1,2,3].

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single backward pass through array; counting zeros is O(n)
Space O(1) In-place modification with only a few integer variables

The algorithm is efficient because it avoids shifting elements repeatedly and requires no extra array allocation.

Test Cases

# Basic examples
assert Solution().duplicateZeros([1,0,2,3,0,4,5,0]) == None  # modifies in-place to [1,0,0,2,3,0,0,4]
assert Solution().duplicateZeros([1,2,3]) == None  # modifies in-place to [1,2,3]

# Edge cases
assert Solution().duplicateZeros([0]) == None  # single zero remains [0]
assert Solution().duplicateZeros([1,0]) == None  # last element zero gets duplicated in place [1,0]
assert Solution().duplicateZeros([0,0,0]) == None  # all zeros, some lost [0,0,0]

# Stress test
arr = [0]*10000
Solution().duplicateZeros(arr)
Test Why
[1,0,2,3,0,4,5,0] General case with multiple zeros
[1,2,3] No zeros to duplicate
[0] Single-element array, zero duplication
[1,0] Zero at the end of array
[0,0,0] All zeros, some overwritten
[0]*10000 Stress test for large array

Edge Cases

One edge case is an array with no zeros. A naive implementation that always shifts elements would unnecessarily overwrite values. Our solution recognizes zero count and avoids unnecessary writes.

Another edge case is zeros at the end of the array. Attempting to duplicate them might push elements out of bounds. The backward iteration ensures we only write within valid indices.

A third edge case is arrays of length one. The algorithm handles this naturally because the backward loop terminates correctly, and no duplication occurs beyond the array bounds. This guarantees correctness even for the smallest input.