algoadvance

Leetcode 1089. Duplicate Zeros

Problem Statement

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note:

• 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]

Clarifying Questions

1. Q: Should the function return anything? A: No, modifications should be made in place.

2. Q: Can the input array contain only zeros? A: Yes, any valid array of integers (including only zeros) will be considered.

3. Q: What is the range of the array length? A: Typically, constraints would fall within a reasonable integer bounds, e.g., 1 <= arr.length <= 10^4.

4. Q: Are there any non-zero constraints on the values inside the array? A: The prompt indicates it’s an integer array, so typical values would be within the range of standard integers.

Strategy

1. Initial Analysis:
   • We need to duplicate every 0 in the array.
   • Non-zero elements must be shifted to the right to make room for the duplicated zero.
   • Directly performing the shifts for each zero in a single pass will be inefficient.
2. Two-Pass Approach:
   • First pass: Determine the effective length of the final array including the duplicated zeros.
   • Second pass: Use a reverse strategy to place elements from the end to avoid overwriting elements while shifting.

Steps:

1. First Pass: Count the zeros and determine the final length including duplicates.
2. Second Pass: Fill the values backwards from the last valid index of the array to ensure elements are not overwritten prematurely.

Code

#include <vector>

void duplicateZeros(std::vector<int>& arr) {
    int n = arr.size();
    
    int zerosToDuplicate = 0;
    int lengthOfNewArray = n;
    
    // First pass to count the number of zeros
    for (int i = 0; i < n; ++i) {
        if (arr[i] == 0) {
            if (i + zerosToDuplicate < n - 1) {
                zerosToDuplicate++;
            } else {
                lengthOfNewArray--;
                break;
            }
        }
    }
    
    for (int i = lengthOfNewArray - 1; i >= 0; --i) {
        if (arr[i - zerosToDuplicate] == 0) {
            if (i < n) {
                arr[i] = 0;
            }
            --i;
            if (i < n) {
                arr[i] = 0;
            }
        } else {
            arr[i] = arr[i - zerosToDuplicate];
        }
    }
}

Time Complexity

• Time Complexity: O(n), because we are iterating over the array a constant number of times.
• Space Complexity: O(1), since we are modifying the array in place with no extra space used proportional to the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?