Day-5 Duplicate Zeroes

Background

This problem statement is a part of Leetcode's Introduction to Data Structures challenge Arrays-101. This is one of the problems under the sub-heading inserting items into an array.

Problem Statement

Given a fixed-length array arr of integers, 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.

Do the above modifications to the input array in place, do not return anything from your function.

Input: [1,0,2,3,0,4,5,0]
Output: null
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

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

Note:

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

Learnings from unsuccessful attempts

Approach 1

1. Iterate over the list.
2. Find the index where value of element is 0.
3. Insert 0 at position index+1.

Problems with Approach 1

1. List.index() - List.index() method returns only the first index if there are multiple occurrences of an element.
2. for element in L: way of for loop doesn't work because index positions are needed as well.
3. The question specifies elements beyond the length of the original array are not written. Hence, by not removing elements my length of the original list was getting increased.
4. Instead of duplicates. Multiple zero's were getting added because there was no check to see if 0 has already been inserted or not.

Approach 2

1. From the original list. Find the index's of each and every zero. Append the index in a new list.
2. Iterate over the new list containing indexes and keep inserting 0's in the original list. At index+1 position.

Problems with Approach 2

1. I didn't go ahead with this thought process because this would mean using extra space. The question specifies that the solution needs to be an in-place solution. Hence, whatever has to be done. Needs to be done with the original array.

By this time I had figured out some of the mistakes. But, not yet figured out a way that would lead to a solution.

Approach 3

1. As indexes were needed. Use this method of iteration for x in range(0, len(arr)): to iterate over the array.
2. Replace List.index() with arr[x]. x is the position. Something like
3. Find the index of the element that has value 0. Insert at position index+1.
4. As mentioned in the question. The length of the original array should not be changed. That means on every insertion pop the last element out of the list.

While some of the earlier problems got solved one of the issues that remained was how to keep track of the newly inserted 0. What if the initial array already has consecutive duplicate zero's? Something like
[1,0,0,2,3,0,4].

Problems with Approach 3

1. As the track of newly inserted zero was not taken care of. Consecutively zero's kept on getting added. Every time zero was encountered. A new 0 got inserted. At the end giving output something like [1,0,0,0,0,0,0]

Woah, again failed. By this attempt mentally I was clear on what things are not working as expected. I was iterating values inside the original array. In that iteration, even the newly inserted 0 was getting considered.

for x in range(0, len(arr)):
    if arr[x]==0:
        L.insert(x+1, arr[x])  #inserts element at x+1 position
        L.pop()                #pop element

Now what this code did was:

1. Let initial arr be [1, 0, 2, 3, 0, 4]
2. After 2nd iteration [1, 0, 0, 2, 3, 0, 4]
3. Now, instead of the next element being 2. It is the newly inserted 0. Hence the array becomes [1, 0, 0, 0, 2, 3]. Hence, the approach fails.

And, then the way was figured out

Solution Approach

1. Initialize a variable to keep a track of newly inserted 0. And in the array iteration. That newly inserted 0 is not to be considered. Hence, only when inserted_index != index than do an insert.

Code Snippet

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        inserted_index = -1
        for index in range(0, len(arr)):
            if inserted_index != index:
                if arr[index] == 0:
                    arr.insert(index+1, arr[index])
                    arr.pop()
                    inserted_index = index + 1
            else:
                continue

Note:

1. This solution is an in-place solution.
2. Time complexity is still 0(n^2) i.e quadratic. Loop 1 - we are iterating over the original array. List.insert() - Insert helps in inserting the value at the mentioned indexes. But, the operation is expensive. 0(n) time complexity.
3. The intention is purposefully to not use any of the external libraries.
4. Just for writing one function why have I used Class? This is not me. That's the default code skeleton on Leetcode.

Question to Discuss

Using Python can time complexity be reduced from Quadratic to Linear? Any alternative to using List.insert() method?

Ps: Replacing List.insert() by shifting all elements to right. It would also be of complexity 0(N).