Sponsored
Sponsored
The two-pointer technique allows us to shift elements efficiently. We use two pointers, one for the original array and one for the new modified version. The first pointer, 'i', traverses the array to count the potential size if zeros were duplicated (up to the length of the array). The second pointer, 'j', keeps track of the position for the final result.
We use these pointers to replicate zeros and copy other elements backward from the end.
Time Complexity: O(n). We go through the array twice, so it's linear with respect to the number of elements.
Space Complexity: O(1). Apart from input, we use a constant amount of extra space.
1class Solution {
2 public void duplicateZeros(int[] arr) {
3 int possibleDups = 0;
4 int length = arr.length - 1;
5 for (int left = 0; left <= length - possibleDups; ++left) {
6 if (arr[left] == 0) {
7 if (left == length - possibleDups) {
8 arr[length] = 0;
9 length -= 1;
10 break;
11 }
12 possibleDups++;
13 }
14 }
15 int last = length - possibleDups;
16 for (int i = last; i >= 0; i--) {
17 if (arr[i] == 0) {
18 arr[i + possibleDups] = 0;
19 possibleDups--;
20 arr[i + possibleDups] = 0;
21 } else {
22 arr[i + possibleDups] = arr[i];
23 }
24 }
25 }
26
27 public static void main(String[] args) {
28 Solution sol = new Solution();
29 int[] arr = {1, 0, 2, 3, 0, 4, 5, 0};
30 sol.duplicateZeros(arr);
31 for (int num : arr) {
32 System.out.print(num + " ");
33 }
34 }
35}
36In Java, the logic mirrors that of both C and C++ with two phases: counting zeros to determine the place to stop shifting elements rightward, and then actually shifting the elements accordingly, processing duplicates in reverse order for optimal in-place modification.
This approach processes the array by creating temporary space for duplicated zeros and then shifting elements accordingly. It uses a separate count to track effective elements and carefully adjusts them in-memory to avoid exceeding the bounds.
Time Complexity: O(n^2). In the worst case, each zero causes a shift of the remaining array.
Space Complexity: O(1). No extra space is used aside from input.
1#include <iostream>
void duplicateZeros(std::vector<int>& arr) {
int idx = 0;
int n = arr.size();
while (idx < n) {
if (arr[idx] == 0) {
for (int j = n - 1; j > idx; --j) {
arr[j] = arr[j - 1];
}
idx++;
}
idx++;
}
}
int main() {
std::vector<int> arr = {1, 0, 2, 3, 0, 4, 5, 0};
duplicateZeros(arr);
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}In C++, the code also inserts zeros by shifting elements repeatedly to accommodate extra zeroes, effectively handling the in-place constraint imposed by direct modifications.