Problem Description

You are given a fixed-length integer array arr. Your task is to duplicate every zero in the array, shifting all remaining elements to the right to make room for the duplicated zeros. Since the array has a fixed length, elements that get pushed beyond the original array length should be discarded.

For example, if you have an array [1, 0, 2, 3, 0, 4], after duplicating zeros it becomes [1, 0, 0, 2, 3, 0]. Notice that:

• The first 0 at index 1 gets duplicated, pushing everything to the right
• The second 0 at index 4 also gets duplicated
• The 4 at the end gets pushed out of the array bounds and is discarded

The key constraints are:

• Modify the array in-place (don't create a new array)
• Don't return anything from the function
• Maintain the original array length
• Only duplicate zeros, not any other numbers

The solution uses a two-pointer technique with two passes:

1. First pass: Count how many elements will fit in the final array by simulating the duplication process
2. Second pass: Fill the array from right to left, placing duplicated zeros where needed

The algorithm handles a special edge case where the last zero to be duplicated might only partially fit in the array (only one copy fits instead of two).

Intuition

The main challenge is that we need to duplicate zeros in-place without using extra space, and we can't simply iterate from left to right because duplicating a zero would overwrite elements we haven't processed yet.

Let's think about what happens when we duplicate zeros. Each zero takes up two positions instead of one, which means some elements at the end will be pushed out of the array. The key insight is that we need to know exactly which elements will remain in the final array before we start modifying it.

Consider this approach: if we know where each element will end up in the final array, we can fill the array backwards. Why backwards? Because when we work from right to left, we won't overwrite any elements we still need to process.

Here's the thought process:

1. First, we need to figure out which elements from the original array will actually fit in the modified array. We can simulate the duplication process by walking through the array and counting positions - regular numbers take 1 position, zeros take 2 positions.

2. Once we know the last element that will fit (let's say it's at index i), we can start filling the array from the rightmost position (j = n-1) backwards.

3. Working backwards, we copy elements from position i to position j. If we encounter a zero, we place it at both positions j and j-1 (duplicating it), then move j two positions left. For non-zero elements, we just copy once.

There's a special edge case: what if the last element that fits is a zero, but only one copy of it fits in the array? The algorithm handles this by checking if our position count k equals n+1 (meaning we went one position over). In this case, we manually place one zero at the last position and adjust our pointers accordingly.

This two-pass approach elegantly solves the problem without requiring extra space and ensures we don't lose any data we still need during the modification process.

Learn more about Two Pointers patterns.

Solution Approach

The solution implements a two-pass algorithm to duplicate zeros in-place:

First Pass - Find the boundary:

n = len(arr)
i, k = -1, 0
while k < n:
    i += 1
    k += 1 if arr[i] else 2

We use two variables:

• i: tracks the current index in the original array
• k: tracks the position count in the final array

Starting from the beginning, we iterate through the array. For each element:

• If it's non-zero (arr[i] != 0), it takes 1 position, so k += 1
• If it's zero, it takes 2 positions (original + duplicate), so k += 2

We stop when k >= n, meaning we've found all elements that will fit in the final array. The variable i now points to the last element from the original array that will appear in the modified array.

Handle Edge Case:

j = n - 1
if k == n + 1:
    arr[j] = 0
    i, j = i - 1, j - 1

If k == n + 1, it means the last element at index i is a zero, but only one copy fits in the array (the second copy would be at position n, which is out of bounds). We handle this by:

• Placing a single 0 at the last position arr[n-1]
• Decrementing both pointers to continue with the remaining elements

Second Pass - Fill the array backwards:

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

Now we fill the array from right to left:

• i points to elements in the original array (moving leftward)
• j points to positions in the final array (moving leftward)

The while ~j condition continues until j becomes -1 (since ~(-1) = 0).

For each element at position i:

• If it's zero, place it at both positions j and j-1 (duplication), then decrement j by an extra step
• If it's non-zero, place it only at position j
• Move both pointers left by 1

This backward filling ensures we never overwrite elements we haven't processed yet, allowing us to modify the array in-place without losing information.

Example Walkthrough

Let's walk through the algorithm with the array [1, 0, 2, 3, 0, 4].

First Pass - Finding the boundary:

We need to determine which elements will fit in the final array after duplicating zeros.

Initial: i = -1, k = 0, n = 6

Step 1: i = 0, arr[0] = 1 (non-zero)
        k = 0 + 1 = 1 (takes 1 position)
      
Step 2: i = 1, arr[1] = 0 (zero)
        k = 1 + 2 = 3 (takes 2 positions)
      
Step 3: i = 2, arr[2] = 2 (non-zero)
        k = 3 + 1 = 4 (takes 1 position)
      
Step 4: i = 3, arr[3] = 3 (non-zero)
        k = 4 + 1 = 5 (takes 1 position)
      
Step 5: i = 4, arr[4] = 0 (zero)
        k = 5 + 2 = 7 (takes 2 positions)
      
Stop! k = 7 > n = 6

After the first pass: i = 4 (pointing to the last 0), k = 7

Handle Edge Case:

Since k = 7 = n + 1, the zero at index 4 only partially fits (only one copy fits).

j = 5 (n - 1)
arr[5] = 0  (place one copy of the zero)
i = 3, j = 4 (adjust pointers)

Array now: [1, 0, 2, 3, 0, 0]
              ↑        ↑     ↑
           unchanged   i     j

Second Pass - Fill backwards:

Now we fill from right to left using elements from index 0 to 3.

Step 1: i = 3, j = 4
        arr[3] = 3 (non-zero)
        arr[4] = 3
        i = 2, j = 3
        Array: [1, 0, 2, 3, 3, 0]
      
Step 2: i = 2, j = 3
        arr[2] = 2 (non-zero)
        arr[3] = 2
        i = 1, j = 2
        Array: [1, 0, 2, 2, 3, 0]
      
Step 3: i = 1, j = 2
        arr[1] = 0 (zero - duplicate it!)
        arr[2] = 0, arr[1] = 0
        j -= 1 (extra decrement for duplication)
        i = 0, j = 0
        Array: [1, 0, 0, 2, 3, 0]
      
Step 4: i = 0, j = 0
        arr[0] = 1 (non-zero)
        arr[0] = 1
        i = -1, j = -1
        Array: [1, 0, 0, 2, 3, 0]

Final result: [1, 0, 0, 2, 3, 0]

The algorithm successfully:

• Duplicated the zero at index 1 → positions 1 and 2
• Partially duplicated the zero at index 4 → only one copy at position 5
• Discarded the element 4 that was pushed out of bounds
• Modified the array in-place without using extra space

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the array.

The algorithm consists of two passes through the array:

• First pass: A while loop that iterates through the array to count how many elements will fit after duplicating zeros. This loop runs at most n times since k increases by at least 1 in each iteration until k >= n. Time: O(n)
• Second pass: Another while loop that fills the array from right to left. The loop condition while ~j continues while j >= 0, iterating through each position exactly once from position n-1 down to 0. Time: O(n)

Total time complexity: O(n) + O(n) = O(n)

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• Variables n, i, k, and j are integer variables that store indices or the array length
• No additional data structures are created
• The modification is done in-place on the input array

The space complexity is constant regardless of the input size, hence O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Edge Case: Last Zero Partial Duplication

The most critical pitfall is not handling the case where the last zero to be included would overflow the array bounds. When counting positions in the first pass, if we end with dest_position == n + 1, it means the last zero at source_index can only have one copy in the array (not both).

Incorrect approach:

# Missing edge case handling - will cause incorrect results
while write_position >= 0:
    if arr[source_index] == 0:
        arr[write_position] = 0
        arr[write_position - 1] = 0  # This might go out of bounds!
        write_position -= 1
    else:
        arr[write_position] = arr[source_index]
    source_index -= 1
    write_position -= 1

Solution: Always check if the last element causes overflow before the second pass:

if dest_position == n + 1:
    arr[write_position] = 0
    source_index -= 1
    write_position -= 1

2. Overwriting Data Before Processing

A common mistake is trying to duplicate zeros from left to right, which overwrites elements that haven't been processed yet.

Incorrect approach:

# This destroys data we haven't processed
for i in range(len(arr)):
    if arr[i] == 0 and i + 1 < len(arr):
        # Shifting right overwrites unprocessed elements
        for j in range(len(arr) - 1, i + 1, -1):
            arr[j] = arr[j - 1]
        arr[i + 1] = 0

Solution: Always process from right to left in the second pass to avoid overwriting unprocessed elements.

3. Off-by-One Errors in Counting

Miscounting the number of positions needed can lead to incorrect array modifications.

Incorrect approach:

# Starting from 0 instead of -1 causes misalignment
source_index = 0  # Wrong initialization
dest_position = 0
while dest_position < n:
    if arr[source_index] == 0:
        dest_position += 2
    else:
        dest_position += 1
    source_index += 1  # Incrementing after check causes issues

Solution: Initialize source_index = -1 and increment before checking the element to maintain proper alignment between counting and actual array indices.

4. Array Index Out of Bounds

When duplicating a zero, accessing write_position - 1 without checking bounds can cause errors.

Incorrect approach:

if arr[source_index] == 0:
    arr[write_position] = 0
    arr[write_position - 1] = 0  # Might be -1 if write_position is 0
    write_position -= 2  # Wrong decrement

Solution: The edge case handling ensures this won't happen, and we should decrement write_position by only 1 extra (not 2) since the loop already decrements it once.

if arr[source_index] == 0:
    arr[write_position] = 0
    arr[write_position - 1] = 0
    write_position -= 1  # Extra decrement for the duplicate
# Regular decrement happens at end of loop