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.
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.
classSolution {
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;
}
}
};
classSolution {
publicvoidduplicateZeros(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
classSolution {
funduplicateZeros(arr: IntArray) {
val n = arr.size
var zeros = arr.count { it==0 }
var i = n - 1var j = n + zeros - 1while (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
classSolution:
defduplicateZeros(self, arr: list[int]) ->None:
n = len(arr)
zeros = arr.count(0)
i, j = n -1, n + zeros -1while i < j:
if j < n:
arr[j] = arr[i]
if arr[i] ==0:
j -=1if j < n:
arr[j] =0 i -=1 j -=1
impl Solution {
pubfnduplicate_zeros(arr: &mut Vec<i32>) {
let n = arr.len();
let zeros = arr.iter().filter(|&&x| x ==0).count();
letmut i = n asisize-1;
letmut j = n asisize+ zeros asisize-1;
while i < j {
if j < n asisize {
arr[j asusize] = arr[i asusize];
}
if arr[i asusize] ==0 {
j -=1;
if j < n asisize {
arr[j asusize] =0;
}
}
i -=1;
j -=1;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution {
duplicateZeros(arr: number[]):void {
constn=arr.length;
letzeros=arr.filter(x=>x===0).length;
leti=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;
}
}
}