Duplicate Zeros

LeetCode Q 1089 - Duplicate Zeros

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.

Do the above modifications to the input array in place, do not return anything from your function.

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

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

Note:

• 1 <= arr.length <= 10000
• 0 <= arr[i] <= 9

Solution

• First pass: we record the total number of zeros in the arr (shift), that is also the shift we need to do. Note we the sum of current index and shift equal to the length of arr, we stop the iteration.

• Second pass: we traverse the array from the last valid index - 1 to the front. Whenever we ecounter a zero, we minus the shift by 1.

Note: in line 9, we need to add the condition i + shift < arr.length again, otherwise test [0,0,0,0,0,0] will cause ArrayIndexOutofBoundaryException.

Code:

public void duplicateZeros(int[] arr) {
  int shift = 0, i = 0;

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

  for (i = i - 1; i >= 0; i--) {
    if (i + shift < arr.length) arr[i + shift] = arr[i];
    if (arr[i] == 0) arr[i + --shift] = arr[i];
  }
}