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

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

It specifically says not to do int result[]=new int[arr.length];. Start by reading the instructions carefully. — Mad Physicist
– Mad Physicist, Commented Aug 12, 2020 at 14:44
You didn't show what is the expected output for the given example arr in your code. — SomeDude
– SomeDude, Commented Aug 12, 2020 at 14:46
I would also move the line " result[loc] = 0; " outside of it's for loop. That only needs to be done once. — Hannah B
– Hannah B, Commented Aug 12, 2020 at 14:56
Thanks,Given solution is working. But if I have to edit my code then i have to write result[loc]=0 outside of all for loop means when all the for loops brackets are closed but then also same output is coming. Or is there anything I have to edit? — Harry
– Harry, Commented Aug 12, 2020 at 15:32

Joni · Accepted Answer · 2020-08-12 15:14:43Z

15

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]);
    }
}

edited Aug 12, 2020 at 15:14

answered Aug 12, 2020 at 15:00

Joni

112k14 gold badges151 silver badges201 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

TomateFraiche Over a year ago

In my opinon, this is a clear example of how a great Stack Overflow answer should look. It is straight to the point, begins with a few essential comments which are followed by a clean piece of code.

serialkiller · Accepted Answer · 2020-08-12 17:11:01Z

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++;
   }
   
}

edited Aug 12, 2020 at 17:11

answered Aug 12, 2020 at 14:53

serialkiller

613 bronze badges

3 Comments

Andy Turner Over a year ago

Wouldn't your inner for loop just fill all the elements after i with zero?

serialkiller Over a year ago

The line you are talking about is outside inner for loop and inside if condition

Andy Turner Over a year ago

no, I'm meaning the loop. Oh, I see, it's not the zero, it's the following element that's copied to the end, e.g. ideone.com/bokEaZ

Poonam Agrawal · Accepted Answer · 2020-12-09 00:31:18Z

2

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;
        }
    }
}

answered Dec 9, 2020 at 0:31

Poonam Agrawal

211 bronze badge

Comments

Asim Kachhap · Accepted Answer · 2021-08-02 01:33:50Z

1

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; 
        }
         
     }
  }
}

answered Aug 2, 2021 at 1:33

Asim Kachhap

112 bronze badges

Comments

Mahalakshmi B S · Accepted Answer · 2023-12-25 10:49:50Z

1

class Solution {
    public void duplicateZeros(int[] arr) {
        Queue<Integer> queue=new LinkedList<Integer>();
        int i=0;
        for(i=0;i<arr.length;i++){
            if(arr[i]==0){
                queue.add(0);
                queue.add(0);
            }else{
                queue.add(arr[i]);
            }
            Integer first=queue.poll();
            arr[i]=first;
        }   
    }
}

answered Dec 25, 2023 at 10:49

Mahalakshmi B S

114 bronze badges

1 Comment

Community Over a year ago

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.

Joop Eggen · Accepted Answer · 2020-08-12 15:07:56Z

0

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;

answered Aug 12, 2020 at 15:07

Joop Eggen

110k8 gold badges89 silver badges142 bronze badges

Comments

hkh · Accepted Answer · 2021-09-06 20:54:45Z

0

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

answered Sep 6, 2021 at 20:54

hkh

4402 gold badges7 silver badges16 bronze badges

Comments

raok1997 · Accepted Answer · 2022-03-10 05:04:59Z

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 ;
}

Kartik Verma · Accepted Answer · 2022-04-29 19:36:43Z

0


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

edited Apr 29, 2022 at 19:36

answered Apr 29, 2022 at 19:31

Kartik Verma

11 bronze badge

Collectives™ on Stack Overflow

Duplicate zero in array by modifying the array in place

Output

9 Answers 9

1 Comment

3 Comments

Comments

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Output

9 Answers 9

1 Comment

3 Comments

Comments

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related