Description

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.

Example 1:

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

Example 2:

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

Constraints:

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 9

Solution

This problem has important constraint that we need to modify the original array without returning new array.

Without In-Place modifications

If the problem was not asking us to modify the array in place, then we could create a new array and then use that array to populate existing array or even return that array. The solution for this approach would look like this.

1create new array result = new int[nums.length]
2int j = 0;
3for i = 0; j < nums.length; i++ // j is likely to reach before or at the same time as i, so check condition on j
4    result[j++] = nums[i]
5    if nums[i] == 0
6        result[j++] = 0;
7return result

 1class Solution {
 2    public int[] duplicateZerosExtraArray(int[] arr) {
 3        int[] result = new int[arr.length];
 4        int j = 0;
 5        for (int i = 0; j < arr.length; i++) {
 6            result[j++] = arr[i];
 7            if (arr[i] == 0) {
 8                result[j++] = 0;
 9            }
10        }
11        return result;
12    }
13}

With In-Place modifications

In this case, we will have to know upfront how many elements will be duplicated such that we can start by ignoring those elements when we start modifying array from the end. To find the number of elements that will be duplicated, we have to iterate through all elements and if we find 0, that means that element will be duplicated. We keep track of these elements in duplicateCounts. If the last element is 0, it will not be duplicated. Also, we don’t touch this element at all, so we reduce length. Also, to ensure this we have to loop until i <= length - duplicateCounts

 1        int duplicateCounts = 0;
 2        int length = arr.length - 1;
 3        for (int i = 0; i <= length - duplicateCounts; i++) {
 4            if (arr[i] == 0) {
 5                if (i == length - duplicateCounts) {
 6                    arr[length] = 0;
 7                    length--;
 8                    break;
 9                }
10                duplicateCounts++;
11            }
12        }

Next, we have to make second pass through elements from the end. This time, we start directly from the last element because we know how many elements will be pushed out based on duplicateCounts. If the element at a given index is 0, we insert two 0s instead of one otherwise insert the element which is present.

1        for (int i = length - duplicateCounts; i >= 0; i--) {
2            if (arr[i] == 0) {
3                arr[i + duplicateCounts] = 0;
4                duplicateCounts--;
5                arr[i + duplicateCounts] = 0;
6            } else {
7                arr[i + duplicateCounts] = arr[i];
8            }
9        }

The full code looks like this.

 1class Solution {
 2    public void duplicateZeros(int[] arr) {
 3        int duplicateCounts = 0;
 4        int length = arr.length - 1;
 5        for (int i = 0; i <= length - duplicateCounts; i++) {
 6            if (arr[i] == 0) {
 7                if (i == length - duplicateCounts) {
 8                    arr[length] = 0;
 9                    length--;
10                    break;
11                }
12                duplicateCounts++;
13            }
14        }
15        for (int i = length - duplicateCounts; i >= 0; i--) {
16            if (arr[i] == 0) {
17                arr[i + duplicateCounts] = 0;
18                duplicateCounts--;
19                arr[i + duplicateCounts] = 0;
20            } else {
21                arr[i + duplicateCounts] = arr[i];
22            }
23        }
24    }
25}