Duplicate Zeros - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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.
Approach 1: Approach 1: Two-Pointer Method
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.
Complexity
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.
Approach 2: Approach 2: Simulate In-Place Shift
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.
Complexity
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 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
1089. Duplicate Zeros - LeetCode Solution • Game of Coders • 29,040 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Duplicate Zeros easy or hard?
Duplicate Zeros Python/Java solution
How to solve Duplicate Zeros in O(n)?
What is the best approach for Duplicate Zeros?
Is Duplicate Zeros asked at Google/Amazon/Meta?
What data structure is used in Duplicate Zeros?
What is the time complexity of Duplicate Zeros?
Ready to solve this problem?
Practice Duplicate Zeros with our built-in code editor and test cases.
Practice on FleetCode