1089. Duplicate Zeros
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 51.6%
Problem Breakdown
The problem requires modifying a fixed-length array in place by duplicating each occurrence of zero while shifting the remaining elements to the right. Elements beyond the length of the original array are not written. The input is an array of integers, and the output is the modified array with zeros duplicated as specified.
Inputs:
- A fixed-length array
arrof integers where1 <= arr.length <= 10000and0 <= arr[i] <= 9.
Outputs:
- The function modifies the input array in place without returning anything.
Implicit Constraints or Tricky Edge Cases:
- If there are no zeros in the array, it remains unchanged.
- If the array is full of zeros, duplicating them might exceed the original length, so only the necessary zeros should be duplicated to fit within the bounds.
- The array’s length constraint is relatively large (up to 10,000), so an efficient solution is crucial.
Intuition
A brute-force approach would involve iterating through the array and duplicating each zero while shifting subsequent elements. However, this approach would require multiple passes over the array and could lead to a time complexity of O(n^2) due to the repeated shifting operations, which is inefficient for large arrays.
The key insight is to first determine how many zeros can be duplicated without exceeding the original length of the array. This allows us to calculate the new positions of elements after duplication and perform a single pass from the end of the array towards the beginning to place elements in their correct positions without overwriting any values prematurely.
Approach
- Count Zeros: Traverse the array to count how many zeros can be duplicated without exceeding the original length.
- Calculate New Length: Determine the effective new length of the array after duplication, considering that some zeros might not be duplicated if they would cause the array to exceed its original bounds.
- Two-Pointer Technique: Use two pointers: one starting from the end of the array (considering the new length) and another from the actual end of the array. Move elements from the second pointer to the first, duplicating zeros as necessary.
- Edge Cases: Handle cases where there are no zeros or when the array is full of zeros.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the array. The algorithm makes a single pass to count zeros and another pass to rearrange elements.
- Space Complexity: O(1), as the solution modifies the array in place without using any additional space proportional to the input size.
Solution
def duplicateZeros(arr):
n = len(arr)
zeros_to_duplicate = 0
# Step 1: Count how many zeros can be duplicated
left = 0
right = n - 1
while left <= right:
if arr[left] == 0:
zeros_to_duplicate += 1
left += 1
# Step 2: Calculate the new length considering the zeros to duplicate
new_length = n + zeros_to_duplicate
# If new_length is greater than the original array length, adjust it
if new_length > n:
arr[n - 1] = 0 # The last element should be zero if it was duplicated
zeros_to_duplicate -= 1
new_length -= 1
# Step 3: Use two pointers to rearrange elements
left = n - 1
right = new_length - 1
while left >= 0:
if arr[left] == 0:
if right < n:
arr[right] = 0
right -= 1
if right < n:
arr[right] = 0
else:
if right < n:
arr[right] = arr[left]
left -= 1
right -= 1
# Example usage:
arr1 = [1, 0, 2, 3, 0, 4, 5, 0]
duplicateZeros(arr1)
print(arr1) # Output: [1, 0, 0, 2, 3, 0, 0, 4]
arr2 = [1, 2, 3]
duplicateZeros(arr2)
print(arr2) # Output: [1, 2, 3]
Edge Cases Handled
- No Zeros: If there are no zeros in the array, it remains unchanged.
- Full of Zeros: If the array is full of zeros, only the necessary zeros are duplicated to fit within the original length.
- Single Element Array: If the array has only one element and it’s zero, it becomes
[0, 0]. - Array Length Exactly Fitting Duplication: If duplicating zeros exactly fits the array length without exceeding it, the function handles this gracefully.