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 that elements beyond the length of the original array are not written. The modification should be done in place and there is no need to return anything from the function.

Clarifying Questions

  1. Input Constraints:
    • What is the length range of the input array?
    • Will there always be at least one zero in the array?

    Answers:

    • The length of the input array can be anything from 1 to 10,000.
    • Not necessarily, the array might contain no zeros.
  2. Output Specifications:
    • Do we need to return the array or modify it in-place?

    Answer:

    • The array should be modified in place; no need to return it.

Strategy

  1. Handle Duplication:
    • Traverse the array to count zeros and identify the end position after duplications.
  2. Shift Elements:
    • Starting from the end, shift elements to their new positions accounting for zero duplications.
  3. Boundary Conditions:
    • Carefully handle array boundaries to ensure elements beyond the array’s length are ignored.

Code

public class DuplicateZeros {
    public void duplicateZeros(int[] arr) {
        int zeros = 0;
        int length = arr.length - 1;

        // Count the number of zeros
        for (int i = 0; i <= length - zeros; i++) {
            if (arr[i] == 0) {
                // Edge case for zero at the boundary
                if (i == length - zeros) {
                    arr[length] = 0;
                    length--;
                    break;
                }
                zeros++;
            }
        }

        // Copy backwards
        int last = length - zeros;
        for (int i = last; i >= 0; i--) {
            if (arr[i] == 0) {
                arr[i + zeros] = 0;
                zeros--;
                arr[i + zeros] = 0;
            } else {
                arr[i + zeros] = arr[i];
            }
        }
    }
}

Time Complexity

Explanation

  1. Counting Zeros:
    • We count zeros while ensuring if there’s a zero at the boundary that will be duplicated and can affect the array length.
  2. Copying Backwards:
    • We start from the end to avoid overwriting elements before they are processed.
    • Handle each element: if it’s zero, duplicate it; otherwise, just shift it to its new position.

This solution ensures the array is modified in place with efficient traversal and in accordance with constraints.

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