Watch 10 video solutions for Duplicate Zeros, a easy level problem involving Array, Two Pointers. This walkthrough by Game of Coders has 28,505 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |