# LeetCode 1089: Duplicate Zeros

## Problem Restatement

We are given an integer array `arr`.

For each zero in the array, we duplicate it and shift all subsequent elements to the right.

Elements beyond the original length are dropped.

We must modify `arr` in-place.

The official constraints state that `1 <= arr.length <= 10^4` and `0 <= arr[i] <= 9`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `arr` (modified in-place) |
| Output | None (modifies `arr`) |
| Rule | Duplicate each zero; drop elements beyond original length |

Function shape:

```python
def duplicateZeros(arr: list[int]) -> None:
    ...
```

## Examples

Example 1:

```python
arr = [1, 0, 2, 3, 0, 4, 5, 0]
```

After duplication: `[1, 0, 0, 2, 3, 0, 0, 4]`.

## Key Insight

Work backwards. First count how many zeros are in `arr[:n]` of the effective output. Then fill from the end.

## Algorithm

1. Count zeros in `arr`.
2. Walk from the end: for each element at `i`, its destination is `i + zeros`. If the destination is within bounds, write it. For zeros, write twice (decrement `zeros` after each write).

## Correctness

By processing right to left, we overwrite elements that have already been placed, not elements we still need.

## Edge Cases

- Check the minimum input size allowed by the constraints.
- Verify duplicate values or tie cases if the input can contain them.
- Keep the return value aligned with the exact failure case in the statement.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Two passes |
| Space | `O(1)` | In-place |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
class Solution:
    def duplicateZeros(self, arr: list[int]) -> None:
        n = len(arr)
        zeros = arr.count(0)
        i = n - 1

        while i >= 0:
            j = i + zeros
            if arr[i] != 0:
                if j < n:
                    arr[j] = arr[i]
            else:
                if j < n:
                    arr[j] = 0
                zeros -= 1
                j -= 1
                if j < n:
                    arr[j] = 0
            i -= 1
```

## Testing

```python
def run_tests():
    s = Solution()

    arr = [1, 0, 2, 3, 0, 4, 5, 0]
    s.duplicateZeros(arr)
    assert arr == [1, 0, 0, 2, 3, 0, 0, 4]

    arr = [1, 2, 3]
    s.duplicateZeros(arr)
    assert arr == [1, 2, 3]

    arr = [0, 0, 0, 0]
    s.duplicateZeros(arr)
    assert arr == [0, 0, 0, 0]

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---|---|
| Mixed zeros | `[1,0,0,2,3,0,0,4]` | Zeros duplicated, tail dropped |
| No zeros | Unchanged | Nothing to duplicate |
| All zeros | Unchanged | Already all zeros |