Duplicate Zeros
What is this problem about?
The Duplicate Zeros coding problem asks you to modify a fixed-length integer array. Every time you encounter a zero, you must duplicate it and shift the remaining elements to the right. Since the array length is fixed, elements shifted beyond the end of the array are discarded. The modifications should ideally be done in-place to save space.
Why is this asked in interviews?
Companies like Microsoft and Amazon ask the Duplicate Zeros interview question to evaluate a candidate's proficiency with two pointers interview pattern and in-place array manipulation. It tests your ability to manage indices without using extra memory. The challenge lies in duplicating elements while moving from left-to-right (which could overwrite data) or right-to-left (which requires pre-calculating the final positions).
Algorithmic pattern used
The most efficient approach uses Two Passes and Two Pointers.
- Pass 1: Count the number of zeros that can actually be duplicated without exceeding the array size.
- Pass 2: Iterate through the array from right to left. Move elements to their new "final" positions. If an element is 0, write it twice at the destination pointer.
This ensures that no data is overwritten before it is moved.
Example explanation
Array: [1, 0, 2, 3, 0, 4, 5, 0]
- First, identify which zeros will be duplicated. The zeros at index 1 and 4 can be duplicated. The zero at index 7 cannot (it's too far right).
- Calculate the virtual end pointer (where the array would end if it weren't fixed-length).
- Start from the original end and move back:
- Move 4 to the end.
- For zero at index 4: Write 0, then another 0.
- Move 3, move 2.
- For zero at index 1: Write 0, then another 0.
- Move 1.
Result:
[1, 0, 0, 2, 3, 0, 0, 4].
Common mistakes candidates make
- Forward Overwriting: Trying to duplicate zeros while iterating from left to right, which overwrites the elements that were supposed to be shifted.
- Incorrect Boundary Handling: Not handling the case where a zero occurs at the very end of the array and can be moved but not duplicated.
- Using Extra Space: Creating a copy of the array (O(N) space) when an in-place solution (O(1) space) is requested.
Interview preparation tip
In-place array problems often require a "count then move" strategy. By calculating the final state first, you can safely perform the operations from right to left, which is a common trick for shifting elements.
