LeetCode 1089: Duplicate Zeros

Problem Restatement

We are given an integer array arr.

For each zero in the array, we duplicate it and shift all subsequent elements to the right.

Elements beyond the original length are dropped.

We must modify arr in-place.

The official constraints state that 1 <= arr.length <= 10^4 and 0 <= arr[i] <= 9.

Input and Output

Function shape:

def duplicateZeros(arr: list[int]) -> None:
    ...

Examples

Example 1:

arr = [1, 0, 2, 3, 0, 4, 5, 0]

After duplication: [1, 0, 0, 2, 3, 0, 0, 4].

Key Insight

Work backwards. First count how many zeros are in arr[:n] of the effective output. Then fill from the end.

Algorithm

1. Count zeros in arr.
2. Walk from the end: for each element at i, its destination is i + zeros. If the destination is within bounds, write it. For zeros, write twice (decrement zeros after each write).

Correctness

By processing right to left, we overwrite elements that have already been placed, not elements we still need.

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

class Solution:
    def duplicateZeros(self, arr: list[int]) -> None:
        n = len(arr)
        zeros = arr.count(0)
        i = n - 1

        while i >= 0:
            j = i + zeros
            if arr[i] != 0:
                if j < n:
                    arr[j] = arr[i]
            else:
                if j < n:
                    arr[j] = 0
                zeros -= 1
                j -= 1
                if j < n:
                    arr[j] = 0
            i -= 1

Testing

def run_tests():
    s = Solution()

    arr = [1, 0, 2, 3, 0, 4, 5, 0]
    s.duplicateZeros(arr)
    assert arr == [1, 0, 0, 2, 3, 0, 0, 4]

    arr = [1, 2, 3]
    s.duplicateZeros(arr)
    assert arr == [1, 2, 3]

    arr = [0, 0, 0, 0]
    s.duplicateZeros(arr)
    assert arr == [0, 0, 0, 0]

    print("all tests passed")

run_tests()