Duplicate Zeros - Leetcode Solution

Problem Description: 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.

Example: Input: [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]

Solution: We can solve this problem by using two pointers. We start by scanning the array to count the number of zeros that need to be duplicated. Then we can use one pointer to move from the end of the array to the beginning while copying elements to the right position. At the same time, we use a second pointer that starts at the end of the array and moves backwards, and for each zero it encounters, it duplicates it.

Let's go through the steps:

Step 1: Count the number of zeros that need to be duplicated

int countZeros = 0;
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == 0) {
        countZeros++;
    }
}

Step 2: Calculate the final length of the modified array

int modifiedLength = arr.length + countZeros;

Step 3: Use two pointers to copy the elements to the right position and duplicate zeros

int i = arr.length - 1;
int j = modifiedLength - 1;
while (i >= 0 && j >= 0) {
    if (arr[i] == 0) {
        arr[j] = 0;
        j--;
        arr[j] = 0;
    } else {
        arr[j] = arr[i];
    }
    i--;
    j--;
}

Step 4: Return the modified array

return arr;

Full solution:

public int[] duplicateZeros(int[] arr) {
    int countZeros = 0;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == 0) {
            countZeros++;
        }
    }
    int modifiedLength = arr.length + countZeros;
    int i = arr.length - 1;
    int j = modifiedLength - 1;
    while (i >= 0 && j >= 0) {
        if (arr[i] == 0) {
            arr[j] = 0;
            j--;
            arr[j] = 0;
        } else {
            arr[j] = arr[i];
        }
        i--;
        j--;
    }
    return arr;
}

Time Complexity: O(n) The time complexity of the solution is O(n) because we need to scan the array once to count the number of zeros, and then we need to copy each element once while duplicating zeros.

Space Complexity: O(1) The space complexity of the solution is O(1) because we are modifying the original array in place and not using any additional data structures.

1