Duplicate Zeros

EASY

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:

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 <= 10⁴
0 <= arr[i] <= 9

Approaches

Checkout 3 different approaches to solve Duplicate Zeros. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Shifting

This is a straightforward but inefficient approach. It iterates through the array from left to right. When a zero is found, it manually shifts all subsequent elements one position to the right to make space for a duplicate zero.

Algorithm

1. Iterate through the array arr with an index i from 0 to n-2.
1. If arr[i] is equal to 0:
1. Start a nested loop with index j from n-1 down to i+1.
1. In the inner loop, assign arr[j] = arr[j-1] to shift elements to the right.
1. Increment i to skip the newly added zero in the next iteration of the outer loop.

The algorithm iterates through the array using an index i. If arr[i] is 0, a nested loop is used to shift elements. This inner loop runs from the end of the array n-1 down to i+1, moving each element arr[j-1] to arr[j]. After shifting, the element at arr[i+1] is now also 0 (the duplicate). To avoid processing this new zero again and causing an infinite loop of duplications, we must increment our main loop index i an extra time. This process repeats until the main loop index i reaches the end of the array.

public void duplicateZeros(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] == 0) {
            // Shift elements to the right
            for (int j = n - 1; j > i; j--) {
                arr[j] = arr[j - 1];
            }
            // We've just inserted a zero at i+1,
            // so we should skip it in the next iteration.
            i++;
        }
    }
}

Complexity Analysis

Time Complexity: O(N^2), where N is the length of the array. In the worst-case scenario (an array filled with zeros), for each of the first N/2 zeros, we perform approximately N/2 shifts, leading to quadratic complexity.Space Complexity: O(1), as the modifications are done in-place without using any significant extra space.

Pros and Cons

Pros:

Simple to conceptualize and implement.
Modifies the array in-place, satisfying the O(1) space constraint.

Cons:

Highly inefficient with a time complexity of O(N^2) in the worst case.
The repeated shifting of elements is a costly operation.

Code Solutions

Checking out 3 solutions in different languages for Duplicate Zeros. Click on different languages to view the code.

class Solution {
public
  void duplicateZeros(int[] arr) {
    int n = arr.length;
    int i = -1, k = 0;
    while (k < n) {
      ++i;
      k += arr[i] > 0 ? 1 : 2;
    }
    int j = n - 1;
    if (k == n + 1) {
      arr[j--] = 0;
      --i;
    }
    while (j >= 0) {
      arr[j] = arr[i];
      if (arr[i] == 0) {
        arr[--j] = arr[i];
      }
      --i;
      --j;
    }
  }
}

Video Solution

Watch the video walkthrough for Duplicate Zeros

Patterns:

Two Pointers

Data Structures:

Array