# Duplicate Zeros
**Difficulty:** EASY
[External](https://leetcode.com/problems/duplicate-zeros)
Canonical: https://scaleengineer.com/dsa/problems/duplicate-zeros
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array
---
## Problem
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 <= 104`
* `0 <= arr[i] <= 9`

# Approaches
## 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.
**Time:** 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:** O(1), as the modifications are done in-place without using any significant extra space.
**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.
### Explanation
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.

```java
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++;
        }
    }
}
```
### Algorithm
- 1. Iterate through the array `arr` with an index `i` from `0` to `n-2`.
- 2. If `arr[i]` is equal to `0`:
- 3.    Start a nested loop with index `j` from `n-1` down to `i+1`.
- 4.    In the inner loop, assign `arr[j] = arr[j-1]` to shift elements to the right.
- 5.    Increment `i` to skip the newly added zero in the next iteration of the outer loop.

## Using an Auxiliary Array
This approach improves the time complexity by using extra space. It creates a new array and populates it based on the rules. It iterates through the input array, copying each element to the new array. If an element is zero, it's copied twice. The process stops once the new array is full. Finally, the contents of the new array are copied back to the original array.
**Time:** O(N), where N is the length of the array. We perform one pass to populate the auxiliary array and another pass to copy it back to the original array. · **Space:** O(N), as we use an auxiliary array of size N to store the result before copying it back.
**Pros:** Achieves a linear time complexity of O(N), which is a significant improvement over the brute-force method.
**Cons:** Requires O(N) extra space for the auxiliary array, which violates the strict in-place modification requirement of the problem.
### Explanation
We use an auxiliary array, `temp`, to build the result. We iterate through the input `arr` with a read pointer `i` and fill `temp` using a write pointer `j`. For each element `arr[i]`, we copy it to `temp[j]`. If `arr[i]` is a zero, we add another zero to `temp` at the next position, provided we don't exceed the array's capacity `n`. After building the `temp` array with the correct final state, we iterate from `0` to `n-1` and copy the elements from `temp` back into the original `arr`.

```java
public void duplicateZeros(int[] arr) {
    int n = arr.length;
    int[] temp = new int[n];
    int i = 0; // read pointer for arr
    int j = 0; // write pointer for temp
    
    while (j < n && i < n) {
        temp[j] = arr[i];
        if (arr[i] == 0) {
            j++;
            if (j < n) {
                temp[j] = 0;
            }
        }
        i++;
        j++;
    }
    
    // Copy temp back to arr
    for (int k = 0; k < n; k++) {
        arr[k] = temp[k];
    }
}
```
### Algorithm
- 1. Create an auxiliary array `temp` of the same size `n` as the input `arr`.
- 2. Initialize a read pointer `i` for `arr` and a write pointer `j` for `temp`, both to `0`.
- 3. Loop while the write pointer `j` is less than `n`.
- 4.    Copy `arr[i]` to `temp[j]`.
- 5.    If `arr[i]` is `0`, increment `j` and, if `j` is still less than `n`, copy another `0` to `temp[j]`.
- 6.    Increment both `i` and `j`.
- 7. After the loop, copy all elements from `temp` back to `arr`.

## Two-Pass, In-Place Optimal Approach
This is the most efficient solution, achieving linear time complexity with constant extra space. It uses a two-pass strategy. The first pass determines the final length and identifies which elements will be kept. The second pass works backward from the end of the array, placing elements into their correct final positions, thus avoiding overwriting data that is still needed.
**Time:** O(N), where N is the length of the array. The algorithm consists of two separate passes, each taking O(N) time, resulting in a total time complexity of O(N) + O(N) = O(N). · **Space:** O(1), as it only uses a few variables for counting and pointers, regardless of the input size. The modification is done in-place.
**Pros:** Optimal solution with O(N) time complexity.; Uses O(1) extra space, satisfying the in-place constraint.; Elegant handling of element placement without overwriting needed data.
**Cons:** Can be less intuitive to understand and implement compared to the more straightforward approaches.; Requires two passes over the array.
### Explanation
This method cleverly solves the problem of overwriting by working backward.

**First Pass:** We count the number of zeros (`zeros`) in the entire array. This helps us determine the final position of each element in a conceptual, expanded array of size `n + zeros`.

**Second Pass:** We use two pointers. A read pointer `i` starts at `n - 1` (the end of the original array), and a write pointer `j` starts at `n + zeros - 1` (the end of the conceptual expanded array). We iterate backward with `i`. At each step, we calculate the position `j` where `arr[i]` should go. If `j` is within the bounds of the actual array (i.e., `j < n`), we write `arr[i]` to `arr[j]`. If `arr[i]` is a zero, we need to write it twice. So, after writing it at `arr[j]`, we decrement `j` again and write another zero at `arr[j]`, provided this new `j` is also within bounds. This backward-writing process ensures that we never overwrite an element before we have read and processed it, because the write pointer `j` will always be greater than or equal to the read pointer `i`.

```java
public void duplicateZeros(int[] arr) {
    int n = arr.length;
    int zeros = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == 0) {
            zeros++;
        }
    }

    int i = n - 1;
    int j = n + zeros - 1;

    while (i >= 0) {
        if (j < n) {
            arr[j] = arr[i];
        }
        
        if (arr[i] == 0) {
            j--; // Decrement write pointer for the duplicate
            if (j < n) {
                arr[j] = 0;
            }
        }
        
        i--;
        j--;
    }
}
```
### Algorithm
- 1. **First Pass:** Iterate through the array from left to right to count the total number of zeros. Let this count be `zeros`.
- 2. **Second Pass:** Initialize a read pointer `i` to `n - 1` and a write pointer `j` to `n + zeros - 1`.
- 3. Loop while `i` is greater than or equal to `0`.
- 4.    If the write pointer `j` is within the array bounds (`j < n`), copy the element `arr[i]` to `arr[j]`.
- 5.    If the element `arr[i]` is a zero, decrement `j` an extra time. If this new `j` is also within bounds, write another zero at `arr[j]`.
- 6.    Decrement both `i` and `j` in each iteration to move to the previous element.

# Solutions
### Java

```java
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;
    }
  }
}

```

### CPP

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

```

### Python

```python
class Solution:
    def duplicateZeros(self, arr: List[int]) -> None: """ Do not return anything, modify arr in-place instead. """ n = len(arr) i, k = - 1, 0 while k < n: i += 1 k += 1 if arr[i] else 2 j = n - 1 if k == n + 1: arr[j] = 0 i, j = i - 1, j - 1 while ~ j: if arr[i] == 0: arr[j] = arr[j - 1] = arr[i] j -= 1 else: arr[j] = arr[i] i, j = i - 1, j - 1

```