Duplicate zeros

Back to index

From the LeetCode problem with the same name. The problem statement is:

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.

If one counts the number of zeros in the whole array first then we know where to put each of the elements. However the tricky part is that – if we start moving elements from the beginning – then we will overwrite elements before we have moved them. The solution is to start moving the elements at the end of the array first. Then we will never be overwriting elements before we move them.

class Solution {
  public void duplicateZeros(int[] arr) {
    int nZeros = 0;
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] == 0) nZeros++;
    }

    int zerosAfter = 0;
    for (int i = arr.length - 1; i >= 0; i--) {
      if (arr[i] == 0) zerosAfter++;
      int zerosBefore = nZeros - zerosAfter;
      int newPosition = i + zerosBefore;
      if (newPosition < arr.length) arr[newPosition] = arr[i];
      if (i != newPosition) arr[i] = 0;
    }
  }
}