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.

Examples

Example 1

1
2
3

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

1
2
3

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^4
  • 0 <= arr[i] <= 9

Solution

Method 1 – Two Pointers (In-Place)

Intuition

We want to duplicate each zero in the array in place, shifting the remaining elements to the right, but not writing beyond the array’s length. We can use two pointers: one to count the number of zeros to be duplicated, and another to write from the end, working backwards to avoid overwriting elements.

Approach

  1. Count the number of zeros to be duplicated, considering the array’s length.
  2. Use two pointers: i (original array end) and j (virtual array end after duplicating zeros).
  3. Move both pointers from the end to the start:
    • If arr[i] is zero, write zero twice (if within bounds), decrement j twice.
    • Otherwise, write the value at j (if within bounds), decrement j.
  4. Continue until i reaches the start.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = arr.size(), zeros = 0;
        for (int i = 0; i < n; ++i) if (arr[i] == 0) ++zeros;
        int i = n - 1, j = n + zeros - 1;
        while (i < j) {
            if (j < n) arr[j] = arr[i];
            if (arr[i] == 0) {
                --j;
                if (j < n) arr[j] = 0;
            }
            --i; --j;
        }
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func duplicateZeros(arr []int) {
    n, zeros := len(arr), 0
    for _, v := range arr {
        if v == 0 {
            zeros++
        }
    }
    i, j := n-1, n+zeros-1
    for i < j {
        if j < n {
            arr[j] = arr[i]
        }
        if arr[i] == 0 {
            j--
            if j < n {
                arr[j] = 0
            }
        }
        i--
        j--
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length, zeros = 0;
        for (int v : arr) if (v == 0) zeros++;
        int i = n - 1, j = n + zeros - 1;
        while (i < j) {
            if (j < n) arr[j] = arr[i];
            if (arr[i] == 0) {
                --j;
                if (j < n) arr[j] = 0;
            }
            --i; --j;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun duplicateZeros(arr: IntArray) {
        val n = arr.size
        var zeros = arr.count { it == 0 }
        var i = n - 1
        var j = n + zeros - 1
        while (i < j) {
            if (j < n) arr[j] = arr[i]
            if (arr[i] == 0) {
                j--
                if (j < n) arr[j] = 0
            }
            i--
            j--
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def duplicateZeros(self, arr: list[int]) -> None:
        n = len(arr)
        zeros = arr.count(0)
        i, j = n - 1, n + zeros - 1
        while i < j:
            if j < n:
                arr[j] = arr[i]
            if arr[i] == 0:
                j -= 1
                if j < n:
                    arr[j] = 0
            i -= 1
            j -= 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn duplicate_zeros(arr: &mut Vec<i32>) {
        let n = arr.len();
        let zeros = arr.iter().filter(|&&x| x == 0).count();
        let mut i = n as isize - 1;
        let mut j = n as isize + zeros as isize - 1;
        while i < j {
            if j < n as isize {
                arr[j as usize] = arr[i as usize];
            }
            if arr[i as usize] == 0 {
                j -= 1;
                if j < n as isize {
                    arr[j as usize] = 0;
                }
            }
            i -= 1;
            j -= 1;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    duplicateZeros(arr: number[]): void {
        const n = arr.length;
        let zeros = arr.filter(x => x === 0).length;
        let i = n - 1, j = n + zeros - 1;
        while (i < j) {
            if (j < n) arr[j] = arr[i];
            if (arr[i] === 0) {
                --j;
                if (j < n) arr[j] = 0;
            }
            --i; --j;
        }
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of arr. Each element is visited at most twice.
  • 🧺 Space complexity: O(1), in-place modification.