Duplicate Zeros LeetCode Problem | JavaScript

This one is a bit tricky question. First, let's look at the problem statement.

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.

Once we understand the problem, Let us have a look at the constraints :

1 <= arr.length <= 10<sup>4</sup>

The array arr will contain at least 1 element and up to 10,000 elements.

0 <= arr[i] <= 9

The elements are single-digit non-negative integers (0 through 9).

Now let us see the solution (JavaScript)

var duplicateZeros = function(arr) {
    let arrayLength = arr.length;
    for (let i = 0; i < arr.length; i++) {
        if(arr[i] === 0){

            for (let a=arr.length ; a > i ; a--){    
                arr[a] = arr[a-1];       
            }
            arr[i+1] = 0;
            i++  
        }
    }
    arr.length = arrayLength;
    return arr;
};

Solution by ChatGPT

If you ask GPT it will give you a different approach to this problem, it uses the 'two-pointer technique' which is a bit long I have mentioned below you can have a look at it:

Optimized Approach:

1. Count the zeros that can be duplicated without exceeding the array bounds.

2. Work backward from the end of the array to place elements in their correct positions.

var duplicateZeros = function(arr) {
    let possibleDups = 0;
    let length = arr.length - 1;

    // Count the zeros that can be duplicated
    for (let left = 0; left <= length - possibleDups; left++) {
        if (arr[left] === 0) {
            // Edge case: This zero can't be duplicated if it's at the edge
            if (left === length - possibleDups) {
                arr[length] = 0; // Move the last zero in place
                length -= 1;
                break;
            }
            possibleDups++;
        }
    }

    // Start backwards from the last element which would be part of the new length
    let last = length - possibleDups;

    // Copy zero twice, and non-zero once
    for (let i = last; i >= 0; i--) {
        if (arr[i] === 0) {
            arr[i + possibleDups] = 0;
            possibleDups--;
            arr[i + possibleDups] = 0;
        } else {
            arr[i + possibleDups] = arr[i];
        }
    }
};

Counting Duplicable Zeros:

First, count how many zeros can be duplicated without exceeding the array bounds by iterating through the array until we reach the point where duplicating another zero would push elements out of bounds.

Placing Elements from the Back:

We start from the back of the array and shift elements to the right place. If we encounter a zero, we place an extra zero.

If the above one is difficult here is a Simplified Two-Pointer Approach:

Count Zeros:

First, we count the number of zeros in the array. This helps us understand how many elements will be shifted.

Backward Traversal:

We traverse the array from the end towards the beginning, using two pointers:

• i points to the current element in the original array.

• j points to the position in the new array where the element should go.

We place elements in their correct position and duplicate zeros by decreasing the j pointer again.

var duplicateZeros = function(arr) {
    let n = arr.length;
    let zeros = 0;

    // Count the number of zeros to be duplicated
    for (let i = 0; i < n; i++) {
        if (arr[i] === 0) {
            zeros++;
        }
    }

    // Work backwards from the end, duplicating zeros as needed
    for (let i = n - 1, j = n + zeros - 1; i >= 0; i--, j--) {
        if (j < n) {
            arr[j] = arr[i];
        }
        if (arr[i] === 0) {
            j--;
            if (j < n) {
                arr[j] = 0;
            }
        }
    }
};

In conclusion, Try to solve the problem yourself and then comment on your optimal solution.