Duplicate Zeros

Difficulty: Easy | Acceptance: 53.60% | Paid: No Topics: Array, Two Pointers

Given a fixed-length integer array arr, 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 and do not return anything.

• Examples
• Constraints
• Brute Force with Extra Array
• In-Place Shifting
• Two Pointers (Optimal)

Examples

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Input: arr = [1,2,3]
Output: [1,2,3]
Explanation: After calling your function, the input array is modified to: [1,2,3]

Constraints

1 <= arr.length <= 10⁴
0 <= arr[i] <= 9

Brute Force with Extra Array

Intuition Create a new array and copy elements from the original, duplicating zeros. Then copy back to the original array.

Steps

• Create a result array
• Iterate through original array, adding each element to result
• If element is zero, add another zero
• Stop when result array reaches original length
• Copy result back to original array

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        n = len(arr)
        result = []
        i = 0
        while len(result) < n:
            result.append(arr[i])
            if arr[i] == 0:
                result.append(0)
            i += 1
        for i in range(n):
            arr[i] = result[i]

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Simple but uses extra space proportional to input size

In-Place Shifting

Intuition Iterate through the array and when a zero is found, shift all elements to the right by one position and insert a duplicate zero.

Steps

• Iterate through the array
• When a zero is encountered, shift all elements after it one position to the right
• Insert a zero at the next position
• Skip the newly inserted zero in the next iteration

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        n = len(arr)
        i = 0
        while i < n:
            if arr[i] == 0:
                for j in range(n - 1, i, -1):
                    arr[j] = arr[j - 1]
                if i + 1 < n:
                    arr[i + 1] = 0
                i += 1
            i += 1

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: In-place but inefficient due to nested shifting operations

Two Pointers (Optimal)

Intuition First pass counts zeros and finds the last valid position. Second pass fills the array from the end, duplicating zeros as needed.

Steps

• First pass: count zeros and find where the last element will land
• Handle edge case where a zero is partially outside the array
• Second pass: iterate backwards, placing elements at their final positions
• Duplicate zeros by placing two zeros when encountered

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        n = len(arr)
        zeros = 0
        left = 0
        
        while left + zeros < n:
            if arr[left] == 0:
                zeros += 1
            left += 1
        
        left -= 1
        right = n - 1
        
        if left + zeros > n - 1:
            arr[right] = 0
            right -= 1
            zeros -= 1
        
        while zeros > 0:
            if arr[left] == 0:
                arr[right] = 0
                right -= 1
                arr[right] = 0
                zeros -= 1
            else:
                arr[right] = arr[left]
            left -= 1
            right -= 1

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Optimal solution with linear time and constant space