Duplicate Zeros — LeetCode 1089 Python Solution

The problem

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.

Example

Input

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

Output

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

Explanation

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

Python solution

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

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 1089. Duplicate Zeros is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems