#1089

Easy

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Duplicate Zeros

Duplicate each zero in a fixed-length array in place, shifting elements right using a two-pointer scanning approach efficiently.

array two pointers

Problem Statement

Given a fixed-length integer array arr, modify it in place so that every occurrence of zero is duplicated, shifting the remaining elements to the right. Any elements that exceed the array length are discarded. This requires careful tracking to avoid overwriting elements during the in-place shifts.

For example, given arr = [1,0,2,3,0,4,5,0], after duplicating zeros in place, the array should become [1,0,0,2,3,0,0,4]. Another example: arr = [1,2,3] remains [1,2,3] since there are no zeros to duplicate. Apply these changes without returning a new array.

Examples

Example 1

Input: arr = [1,0,2,3,0,4,5,0]

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

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]

After calling your function, the input array is modified to: [1,2,3]

Constraints

1 <= arr.length <= 104
0 <= arr[i] <= 9

Solution Approach

Count zeros to determine shifts

Scan the array to count how many zeros will need duplication. Use this count to calculate the final position for each element. This ensures that shifting elements right preserves the original values without extra storage.

Two-pointer scanning from end

Set one pointer at the end of the original array and another at the effective end after duplication. Move backward, copying or duplicating zeros to their correct positions, preventing overwrites. This aligns with the two-pointer invariant tracking pattern.

Handle edge zeros carefully

If a zero would overflow the array length after duplication, only write the zero once. This avoids writing beyond the array boundary and ensures correctness, which is the main failure mode in Duplicate Zeros problems.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

Time complexity is O(N) because each element is scanned at most twice, and space complexity is O(1) since all operations modify the array in place without extra arrays or buffers.

What Interviewers Usually Probe

Are you tracking how duplicating zeros affects element positions?
Can you solve this in-place without extra storage?
How do you handle zeros at the end that would overflow the array?

Common Pitfalls or Variants

Common pitfalls

Overwriting elements before they are duplicated when scanning left to right.
Failing to handle zeros at the last valid index correctly, causing array overflow.
Using extra arrays which violates the in-place modification requirement.

Follow-up variants

Duplicate a specific value other than zero while shifting elements in place.
Duplicate zeros but allow dynamic array expansion instead of fixed length.
Count the total duplicates of zeros without modifying the original array in place.

FAQ

What is the key pattern used to solve Duplicate Zeros?

The problem relies on two-pointer scanning with invariant tracking to shift and duplicate zeros without overwriting elements.

Can this be done without extra space?

Yes, the solution modifies the array in place with O(1) extra space by scanning from the end and duplicating zeros carefully.

What happens if a zero is at the last index?

If duplicating that zero would exceed the array length, write it only once to prevent overflow, following the edge-case handling pattern.

Is this approach efficient for large arrays?

Yes, time complexity is O(N) since each element is visited at most twice, making it efficient for arrays up to the constraint limit.

How does GhostInterview explain in-place modifications?

It guides step-by-step how to track element positions, count zeros, and apply two-pointer scanning, ensuring correct in-place duplication.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        n = len(arr)
        i, k = -1, 0
        while k < n:
            i += 1
            k += 1 if arr[i] else 2
        j = n - 1
        if k == n + 1:
            arr[j] = 0
            i, j = i - 1, j - 1
        while ~j:
            if arr[i] == 0:
                arr[j] = arr[j - 1] = arr[i]
                j -= 1
            else:
                arr[j] = arr[i]
            i, j = i - 1, j - 1

Solution 2

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        n = len(arr)
        i, k = -1, 0
        while k < n:
            i += 1
            k += 1 if arr[i] else 2
        j = n - 1
        if k == n + 1:
            arr[j] = 0
            i, j = i - 1, j - 1
        while ~j:
            if arr[i] == 0:
                arr[j] = arr[j - 1] = arr[i]
                j -= 1
            else:
                arr[j] = arr[i]
            i, j = i - 1, j - 1

Continue Practicing

#1048 longest string chain #1023 camelcase matching #986 interval list intersections