Problem statement

https://leetcode.com/problems/duplicate-zeros/

Solution

In my opinion quite lengthy problem for easy problem. Idea is to use two pointers. We not allowed to use additional space and we do not know in advance where we finish, so we need to use two passes. On the first pass we find number of zeroes which will be duplicated, that is dups. On the second pass go from the end and add zeroes.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def duplicateZeros(self, arr):
        dups, n = 0, len(arr) - 1
        for lft in range(n + 1):
            if lft > n - dups: break
            if arr[lft] == 0:
                if lft == n - dups:
                    arr[n] = 0
                    n -= 1
                    break
                dups += 1
            
        for i in range(n - dups, -1, -1):
            if arr[i] == 0:
                arr[i + dups] = 0
                dups -= 1
                arr[i + dups] = 0
            else:
                arr[i + dups] = arr[i]