Duplicate Zeros
EasyPrompt
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 <= 1040 <= arr[i] <= 9
Approaches
3 approaches with complexity analysis and trade-offs.
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
-
- Iterate through the array
arrwith an indexifrom0ton-2.
- Iterate through the array
-
- If
arr[i]is equal to0:
- If
-
- Start a nested loop with index
jfromn-1down toi+1.
- Start a nested loop with index
-
- In the inner loop, assign
arr[j] = arr[j-1]to shift elements to the right.
- In the inner loop, assign
-
- Increment
ito skip the newly added zero in the next iteration of the outer loop.
- Increment
Walkthrough
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
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.
Trade-offs
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.
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.
Algorithm
-
- Create an auxiliary array
tempof the same sizenas the inputarr.
- Create an auxiliary array
-
- Initialize a read pointer
iforarrand a write pointerjfortemp, both to0.
- Initialize a read pointer
-
- Loop while the write pointer
jis less thann.
- Loop while the write pointer
-
- Copy
arr[i]totemp[j].
- Copy
-
- If
arr[i]is0, incrementjand, ifjis still less thann, copy another0totemp[j].
- If
-
- Increment both
iandj.
- Increment both
-
- After the loop, copy all elements from
tempback toarr.
- After the loop, copy all elements from
Walkthrough
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.
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]; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
-
- First Pass: Iterate through the array from left to right to count the total number of zeros. Let this count be
zeros.
- First Pass: Iterate through the array from left to right to count the total number of zeros. Let this count be
-
- Second Pass: Initialize a read pointer
iton - 1and a write pointerjton + zeros - 1.
- Second Pass: Initialize a read pointer
-
- Loop while
iis greater than or equal to0.
- Loop while
-
- If the write pointer
jis within the array bounds (j < n), copy the elementarr[i]toarr[j].
- If the write pointer
-
- If the element
arr[i]is a zero, decrementjan extra time. If this newjis also within bounds, write another zero atarr[j].
- If the element
-
- Decrement both
iandjin each iteration to move to the previous element.
- Decrement both
Walkthrough
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.
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--; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; } }}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; } }};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 - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.