Code Implementation

class Solution:
    def duplicateZeros(self, arr):
        n = len(arr)
        zeros = 0
        for num in arr:
            if num == 0:
                zeros += 1
        i = n - 1
        j = n + zeros - 1
        while i < j:
            if j < n:
                arr[j] = arr[i]
            if arr[i] == 0:
                j -= 1
                if j < n:
                    arr[j] = 0
            i -= 1
            j -= 1

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size();
        int zeros = 0;
        for (int num : arr) {
            if (num == 0) zeros++;
        }
        int i = n - 1;
        int j = n + zeros - 1;
        while (i < j) {
            if (j < n) arr[j] = arr[i];
            if (arr[i] == 0) {
                j--;
                if (j < n) arr[j] = 0;
            }
            i--;
            j--;
        }
    }
};

class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int zeros = 0;
        for (int num : arr) {
            if (num == 0) zeros++;
        }
        int i = n - 1;
        int j = n + zeros - 1;
        while (i < j) {
            if (j < n) arr[j] = arr[i];
            if (arr[i] == 0) {
                j--;
                if (j < n) arr[j] = 0;
            }
            i--;
            j--;
        }
    }
}

var duplicateZeros = function(arr) {
    let n = arr.length;
    let zeros = 0;
    for (let num of arr) {
        if (num === 0) zeros++;
    }
    let i = n - 1;
    let j = n + zeros - 1;
    while (i < j) {
        if (j < n) arr[j] = arr[i];
        if (arr[i] === 0) {
            j--;
            if (j < n) arr[j] = 0;
        }
        i--;
        j--;
    }
};

Problem Description

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. The modifications must be done in-place and with O(1) extra space.

• Each time you encounter a zero, duplicate it, and shift the subsequent elements to the right.
• Elements that would "fall off" the end of the array are discarded.
• Do not return anything from your function; modify arr in-place.
• There is only one valid solution for each input.

Thought Process

At first glance, it seems natural to iterate through arr and, whenever we find a zero, insert another zero after it, shifting all subsequent elements to the right. However, this approach requires shifting many elements multiple times, which is inefficient.

Since the array has a fixed length, adding new elements at the end is not possible. Also, we must modify the array in-place, so we cannot use extra space proportional to the array's size.

The challenge is to efficiently duplicate zeros without overwriting values that haven't been processed yet. This leads to the idea of working from the end of the array backwards, so that we can copy or duplicate elements into their final positions without losing any data.

Solution Approach

To solve this problem efficiently and in-place, we use a two-pass algorithm:

1. Count the zeros: First, iterate through the array to count the total number of zeros. This helps us determine how much the array would "grow" if we had infinite space.
2. Backward pass to shift and duplicate: Use two pointers: one at the end of the original array (i) and one at the position where the element would go if the array could expand to fit all duplicates (j). Move both pointers backwards. If the element at i is not zero, copy it to j (if j is within bounds). If it is zero, write zero twice (again, only if the index is within bounds), and move j backwards accordingly.

This approach ensures that each element is written at most once, and we never overwrite unprocessed data.

Example Walkthrough

Let's consider the input: arr = [1,0,2,3,0,4,5,0]

1. Count zeros: There are 3 zeros.
2. Set pointers: i = 7 (last index), j = 7 + 3 = 10.
3. Backward pass:
   • i=7, arr[7]=0: j=10 (out of bounds), j=9 (out of bounds), j=8 (out of bounds), decrement i and j.
   • i=6, arr[6]=5: j=7, write arr[7]=5.
   • i=5, arr[5]=4: j=6, write arr[6]=4.
   • i=4, arr[4]=0: j=5, write arr[5]=0; j=4, write arr[4]=0.
   • i=3, arr[3]=3: j=3, write arr[3]=3.
   • i=2, arr[2]=2: j=2, write arr[2]=2.
   • i=1, arr[1]=0: j=1, write arr[1]=0; j=0, write arr[0]=0.

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

Time and Space Complexity

• Brute-force approach: For each zero, shift all elements to the right. In the worst case (all zeros), this takes O(n^2) time.
• Optimized approach (two-pointer backward): Each element is visited at most twice (once for counting, once for copying), so the time complexity is O(n).
• Space complexity: Both approaches work in-place, so space complexity is O(1).

Summary

The key insight for the Duplicate Zeros problem is to process the array from the end, using a two-pointer technique to avoid overwriting data. By first counting the zeros, we can determine where each element should go, and by working backwards, we ensure in-place duplication without extra space or repeated shifting. This leads to an elegant O(n) time and O(1) space solution.