easy

Duplicate Zeros

Duplicate every zero in place, shifting later values right.

1. Define the problem

Duplicate Zeros

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. First count how many zeros fit within bounds , then fill the array from the back so nothing gets overwritten before it is read.

Constraints

  • 1 ≤ arr.length ≤ 104
  • 0 ≤ arri ≤ 9

Example

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

Explanation Every 0 is duplicated and everything shifts right, with values pushed past the end simply dropped.

2. Know the words first

In plain terms

In place
Making the change directly inside the given array instead of building a new one, using little to no extra memory.
Fit within bounds
Only counting duplicated zeros that would still land inside the original array length, since values pushed past the end are simply dropped.
3. Visualize the solution

Fill from the back after counting zeros within bounds

Fill from the back after counting zeros within bounds
Statusinit

read=7 (value 0), write=7. Write 0 at write, then write 0 at write-1=6, read moves to 6, write to 5.

What happens in this step

read = 7 (value 0), write = 7

Value is 0: write 0 to index 7, then also write 0 to index 6 (the duplicate). read -> 6, write -> 5.
Step 1 of 4

Steps to visualize

  1. Walk the array from the front, counting each zero found within the original length.
  2. Working from the back of the array, copy values from the read pointer to the write pointer.
  3. If the value being copied is 0, write it twice (once at write, once at write - 1) and move the read pointer once.
  4. Continue until every original element has been placed.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Fill from the back after counting zeros within bounds
Statusinit

read=7 (value 0), write=7. Write 0 at write, then write 0 at write-1=6, read moves to 6, write to 5.

What happens in this step

read = 7 (value 0), write = 7

Value is 0: write 0 to index 7, then also write 0 to index 6 (the duplicate). read -> 6, write -> 5.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function duplicateZeros(arr) {
  const n = arr.length;
  let possibleDups = 0;
  let last = n - 1;

  for (let left = 0; left <= last - possibleDups; left++) {
    if (arr[left] === 0) {
      if (left === last - possibleDups) {
        arr[last] = 0;
        last--;
        break;
      }
      possibleDups++;
    }
  }

  let read = last - possibleDups;
  let write = last;

  while (read >= 0) {
    if (arr[read] === 0) {
      arr[write] = 0;
      write--;
      arr[write] = 0;
    } else {
      arr[write] = arr[read];
    }

    write--;
    read--;
  }

  return arr;
}
Time
O(n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
arr = [1, 0, 2, 3, 0, 4, 5, 0][1, 0, 0, 2, 3, 0, 0, 4]example from the docstring
arr = [1, 2, 3][1, 2, 3]no zeros present, array is unchanged
arr = [0, 0, 0, 0][0, 0, 0, 0]every element is zero
arr = [0][0]smallest valid input, a single zero that has nowhere to duplicate into
arr = [8, 4, 5, 0, 0, 0, 0, 7][8, 4, 5, 0, 0, 0, 0, 0]zeros near the end cause overflow duplicates to be dropped
arr = [9][9]smallest valid input, a single non-zero value

Keep reading