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] <= 9Problem Overview: You are given a fixed-length integer array. Every time a 0 appears, duplicate it and shift the remaining elements to the right. Elements that move past the array boundary are discarded. The modification must happen in-place without returning a new array.
The main challenge is handling shifts without overwriting values you still need to process. Since the array size cannot change, you must carefully manage how elements move while staying within bounds. This makes the problem a good exercise in array manipulation and careful pointer movement.
Approach 1: Two-Pointer Method (O(n) time, O(1) space)
This is the optimal solution. First scan the array and count how many zeros will be duplicated. This tells you how far elements will effectively shift. Then use two pointers: one starting from the original array end and another from the "virtual" end after duplication. Move backward so values are written safely without overwriting unprocessed elements. When the left pointer hits a zero, write two zeros while adjusting bounds if the virtual index exceeds the array size.
The key insight is processing from right to left. Writing from the back guarantees that elements not yet processed remain untouched. This turns what looks like repeated shifting into a single linear pass. The algorithm runs in O(n) time with O(1) extra space and is a classic two pointers technique.
Approach 2: Simulate In-Place Shift (O(n^2) time, O(1) space)
This straightforward method scans the array from left to right. Whenever you encounter a zero, shift every element to its right one position forward, starting from the end of the array. After the shift, place another zero in the next position and skip over the duplicated pair. Because the array length is fixed, the last element is dropped during the shift.
This approach mirrors exactly how you might perform the operation manually. However, each zero triggers a full right shift, which costs O(n). In the worst case, many zeros cause repeated shifts, resulting in O(n^2) time complexity. Space usage remains O(1) since the operation modifies the array directly.
Recommended for interviews: The two-pointer solution is what most interviewers expect. It demonstrates strong control over in-place array operations and avoids unnecessary shifting. Showing the shift-based approach first can demonstrate understanding of the mechanics, but the O(n) two-pointer optimization shows algorithmic maturity and efficiency.
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.
The solution uses a two-pass method. The first pass counts the number of zeros and calculates the new length by incorporating the duplicating zeros, without exceeding the original array's bounds. The second pass migrates elements from the end to start, duplicating zeros when they appear.
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.
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.
This C solution simulates the shifting of elements in place by inserting extra zero wherever required. It temporarily shifts each element to make space for duplication effectively.
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.
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pointer Method | Time Complexity: O(n). We go through the array twice, so it's linear with respect to the number of elements. |
| Approach 2: Simulate In-Place Shift | Time Complexity: O(n^2). In the worst case, each zero causes a shift of the remaining array. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Method | O(n) | O(1) | Best general solution. Efficient when modifying arrays in-place without repeated shifts. |
| Simulate In-Place Shift | O(n^2) | O(1) | Useful for understanding the mechanics of the problem or for very small arrays. |
1089. Duplicate Zeros - LeetCode Solution • Game of Coders • 28,505 views views
Watch 9 more video solutions →Practice Duplicate Zeros with our built-in code editor and test cases.
Practice on FleetCode