Duplicate Zeros

Problem Statement

The task is to modify an integer array named arr by duplicating each occurrence of the number zero. When a zero is duplicated, the elements that follow are shifted to the right. It is important to note that the modifications should adjust within the array's initial length, meaning any elements that would shift outside the array's bounds due to duplication should not be included. These changes should happen directly within the input array, hence altering it in-place without returning any new output. Additionally, take into account that only the zeros are duplicated, and each duplication should reflect immediately in the array.

Examples

Example 1

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]

Example 2

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 <= 104
• 0 <= arr[i] <= 9

Approach and Intuition

The nature of the problem requires us to analyze and possibly modify the array as we iterate through it. Given the need to double every zero encountered and shift subsequent items, direct array modification without additional storage consideration calls for a careful approach to ensure no data loss:

1. Start by identifying the positions of zeroes that can be duplicated without exceeding the array limit. This involves reverse iterations or marking schemes.
2. From the last element of the array, shift elements to the right whenever a zero is duplicated. This back-to-front method avoids overwriting elements that haven't been processed.
3. Specifically treat cases with no zeros with a gentle bypass, ensuring minimal performance hit on such datasets.

This is a simplified intuition of how to address the problem respecting the original array’s constraints while ensuring maximum efficiency.

Solutions

class Solution {
    public void expandZeros(int[] data) {
        int zeroCount = 0;
        int originalLength = data.length - 1;

        // Calculate number of zeros that can be duplicated
        for (int i = 0; i <= originalLength - zeroCount; i++) {
            if (data[i] == 0) {
                if (i == originalLength - zeroCount) {
                    data[originalLength] = 0;
                    originalLength -= 1;
                    break;
                }
                zeroCount++;
            }
        }

        // Duplicate zeros from the end to start in the array space
        int end = originalLength - zeroCount;
        for (int j = end; j >= 0; j--) {
            if (data[j] == 0) {
                data[j + zeroCount] = 0;
                zeroCount--;
                data[j + zeroCount] = 0;
            } else {
                data[j + zeroCount] = data[j];
            }
        }
    }
}