Duplicate Zeros

easy array two pointers in-place

Problem

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right. Elements beyond the length of the original array are not written. Do the modifications to the input array in place and do not return anything.

Inputarr = [1, 0, 2, 3, 0, 4]

Output[1, 0, 0, 2, 3, 0]

The zeros at indices 1 and 4 are duplicated; the trailing 0 and the 4 are pushed past the end and dropped.

arr (comma-separated)

def duplicate_zeros(arr):
    n = len(arr)
    zeros = arr.count(0)
    write = n + zeros - 1
    for read in range(n - 1, -1, -1):
        if write < n:
            arr[write] = arr[read]
        write -= 1
        if arr[read] == 0:
            if write < n:
                arr[write] = 0
            write -= 1

function duplicateZeros(arr) {
  const n = arr.length;
  let zeros = arr.filter(x => x === 0).length;
  let write = n + zeros - 1;
  for (let read = n - 1; read >= 0; read--) {
    if (write < n) arr[write] = arr[read];
    write--;
    if (arr[read] === 0) {
      if (write < n) arr[write] = 0;
      write--;
    }
  }
}

class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length, zeros = 0;
        for (int x : arr) if (x == 0) zeros++;
        int write = n + zeros - 1;
        for (int read = n - 1; read >= 0; read--) {
            if (write < n) arr[write] = arr[read];
            write--;
            if (arr[read] == 0) {
                if (write < n) arr[write] = 0;
                write--;
            }
        }
    }
}

void duplicateZeros(vector<int>& arr) {
    int n = arr.size(), zeros = 0;
    for (int x : arr) if (x == 0) zeros++;
    int write = n + zeros - 1;
    for (int read = n - 1; read >= 0; read--) {
        if (write < n) arr[write] = arr[read];
        write--;
        if (arr[read] == 0) {
            if (write < n) arr[write] = 0;
            write--;
        }
    }
}

Explanation

We must duplicate every zero in place, pushing later values to the right and dropping whatever falls off the end. The tricky part is doing it without an extra array. The clever move is to copy values from the back of the array toward the front, so we never overwrite something we still need to read.

First we count how many zeros there are. If we imagine the array were long enough, the final length would be n + zeros. We set a write pointer to that imaginary last index (n + zeros - 1) and a read pointer at the real last index.

Walking backwards, we copy arr[read] to position write, but only actually store it when write < n (positions at or beyond n are off the end and get discarded). After writing we move write left. If the value we just read was a zero, we write a second zero and move write left again.

Example: arr = [1, 0, 2, 3, 0, 4]. Going from the back, the 4 and the trailing 0 get pushed past the end and dropped; each remaining zero gets doubled. The array becomes [1, 0, 0, 2, 3, 0].

Because we move each pointer across the array just once, the whole thing finishes in one backward sweep using no extra space.

Time: O(n) Space: O(1)