Duplicate zero in array by modifying the array in place

Question

There is a fixed length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right. The elements beyond the length of the original array are not written.

We have to modify input array in place and doesn't have to create new array.

So I created that but it is duplicating the zero which is at the end of array and not the previous zeros. Can somebody help me with this?

public static void addPos() {
    int arr[] = { 1, 2, 0, 3, 0, 5, 0, 7, 8 };
    int result[] = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == 0) {
            int loc = i;
            for (int j = 0; j < loc; j++) {
                result[j] = arr[j];
                result[loc] = 0;
            }
            for (int j = loc + 1; j < arr.length; j++) {
                result[j] = arr[j - 1];
            }
        }
    }
    for (int k = 0; k < arr.length; k++)
        System.out.println(result[k]);
}

Output

1
2
0
3
0
5
0
0
7

Expected output:
1
2
0
0
3
0
0
5
0

Answer 1

Every iteration of the loop overwrites the results from the previous iteration, so the end result only shows the results from the last iteration, which duplicates the last 0 is duplicated.

One way to solve this is by iterating backwards "right to left". It simplifies a lot of things. You can get rid of the auxiliary result array. The basic idea is, go backwards in the array, and every time you find a 0, you duplicate it by rewriting the array to the right of the zero.

public static void addPos() {
    int arr[] = {1, 2, 0, 3, 0, 5, 0, 7, 8};

    for (int i = arr.length - 1; i >= 0; i--) {
        if (arr[i] == 0) {
            // duplicate it!
            for (int j = arr.length - 1; j > i; j--) {
                arr[j] = arr[j-1];
            }
        }
    }

    for (int k = 0; k < arr.length; k++) {
        System.out.println(arr[k]);
    }
}

Answer 2

The for loop keeps overwriting the values in result array, hence the result shows only last duplication.You should not be using the result array at all.Keep shipting values in the original array itself.

You can refer to below code.

for(int i=0;i<arr.length-1;i++){
  if(arr[i]==0){
    for(int j=arr.length-1;j>i;j--){
    arr[j]=arr[j-1];
     }
     i++;
   }
   
}

Answer 3

public void duplicateZeros(int[] arr)

{ int i=0;

    while(i<arr.length)
    {
        
        if(arr[i]==0)
        {
            int j=arr.length-1;
            while(j != i)
            {
                arr[j]=arr[j-1];
                j--;
            }
            i=i+2;
        }
        else
        {
            i=i+1;
        }
    }
}

    

Answer 4

So one has this:

int[] arr = { 1, 2, 0, 3, 0, 5, 0, 7, 8 };

public static void duplicateZeros(int[] arr) {

and should get

{ 1, 2, 0, 3, 0, 5, 0, 7, 8 }
        v___
{ 1, 2, 0, 0, 3, 0, 5, 0, 7 }
                 v___
{ 1, 2, 0, 0, 3, 0, 0, 5, 0 }

This looks like:

for (int i = 1; i < n; ++i) {
    if (arr[i - 1] == 0) {
        insert at i a 0;
    }
}

insert at i a 0:
    // First move the remaining to the right: i .. n-2
    ...
    // Then fill in the zero
    arr[i] = 0;

Answer 5

Without using any other Array.

class Solution {
public void duplicateZeros(int[] arr) {
    for(int i=0;i<arr.length;i++){
        if(arr[i]==0){
            
            for(int j=arr.length-1;j>i;j--){
                arr[j]=arr[j-1];   
            }
            i=i+1; 
        }
         
     }
  }
}

Answer 6

Python solution for anyone interested adapted from here

the solution is non-trivial if you do not separate the action of the pointer iterating over the list and the insertions. It's very easy to write a for-loop that adds 0's ad-infinitum.

def duplicateZeros(arr):

    # define the incrementor
    i = 0

    # loop through all dynamic elements
    while i < len(arr)-1:
        # if the character is a zero
        if arr[i]==0:
            # remove the last item from the array
            arr.pop()
            # insert a zero in front of current element
            arr.insert(i+1, 0)
            # move one place forward
            i += 1

        # increment to the next character
        i += 1

Answer 7

Solution 1: Loop from start to end. If zero is found, move the elements from next index and fill the next as zero and skip next.

public static void duplicateZeros(int[] arr) {
    System.out.println("BEGIN duplicateZeros:" + Arrays.toString(arr));

    for(int i=0; i<arr.length-1; ++i) {
        if (arr[i] == 0) {
            move(arr, i);
            ++i;
        }
    }
    
    System.out.println("END duplicateZeros:" + Arrays.toString(arr) +"\n");
}

private static void move(int[] arr, int index) {
    // move to the right from index+1
    for(int i=arr.length-1; i>index; i--) {
        arr[i] = arr[i-1];
    }
    
    // fill 0 at index
    arr[index] = 0 ;
}

Solution2: Loop from end to start. If zero is found, move the elements from next index and fill the current index as zero.

public static void duplicateZeros(int[] arr) {
    System.out.println("BEGIN duplicateZeros:" + Arrays.toString(arr));
    
    for(int i=arr.length-1; i>=0; i--) {
        if (arr[i] == 0) {
            move(arr, i);
        }
    }
    
    System.out.println("END duplicateZeros:" + Arrays.toString(arr) +"\n");
}

private static void move(int[] arr, int index) {
    // move to the right from index+1
    for(int i=arr.length-1; i>index; i--) {
        arr[i] = arr[i-1];
    }
    
    // fill 0 at index
    arr[index] = 0 ;
}

Answer 8

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """
        if len(arr)==0:
            return arr
        index = 0
        while index < len(arr):
            print(index,end=" ")
            if arr[index]==0:
                arr.insert(index+1,0)
                arr.pop()
                index+=1
            index+=1