Problem Description
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.
Key Insights
- Each zero in the array should be duplicated, which means that the elements following a zero will shift to the right.
- The array modification must be done in place without using additional space for another array.
- We need to account for the fact that duplicating zeros may cause the array to exceed its original length, so we must handle this carefully.
Space and Time Complexity
Time Complexity: O(n), where n is the length of the array. We make a single pass through the array to determine how many elements need to be shifted. Space Complexity: O(1), since we are modifying the array in place and not using any additional data structures that grow with input size.
Solution
To solve the problem, we can use a two-pass approach. In the first pass, we will count how many zeros are present in the array within the bounds of the original length. In the second pass, we will go through the array in reverse, duplicating the zeros and shifting elements to the right.
We can maintain two pointers: one for the current index in the original array and one for the index where we will write the modified values. By iterating from the end of the array to the beginning, we can avoid overwriting elements that we still need to process.