Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right

Question

I wrote this code, it passed initial test cases but it shows run time error when I submitted. I am unable to understand why? Run time error:- Index -1 array out of bounds for length 8

class Solution {
public int[] duplicateZeros(int[] arr) 
{
    int n=arr.length;
    int count=0;
    for(int i=0;i<n;i++)
    {
        if(arr[i]==0)
            count=count+1;
    }
    
    int loc= n-1;
    int p=n-1+count;
    if(count==0)
        return arr;
    for(int i=n-1,j=p;i>=0;i--,j--)
    {
        if(j<=n && loc>=0)
        {
            if(arr[i]==0)
            {
                arr[loc]=0;
                arr[loc-1]=0;
                loc=loc-2;
            }
            else
            {
                arr[loc]=arr[i];
                loc=loc-1;
            }
        }
    }
    return arr;

} }

An array is fixed length - when you are shifting elements to the right are you expected to enlarge the array or do the shifted elements get dropped from the array? Please add the input for success and failure cases. — vsfDawg
– vsfDawg, Commented Aug 12, 2021 at 10:53

Davide Lorenzo MARINO · Accepted Answer · 2021-08-12 10:42:25Z

1

In the following code if loc is 0 and arr[i] is 0 and j <= n you enter the nested if and arr[loc-1] is arr[-1] that can give you the ArrayOutOfBoundException

// If j <= n and loc is 0 enter the first if
if (j <= n && loc >= 0) {
   // If arr[i] == 0 enter the second if
   if (arr[i] == 0) {
       arr[loc] = 0;
       arr[loc - 1] = 0;   // loc is 0 so arr[loc - 1] throw the Error
       loc = loc - 2;
   } ...

answered Aug 12, 2021 at 10:42

Davide Lorenzo MARINO

27k4 gold badges45 silver badges58 bronze badges

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

Comments

Watachiaieto · Accepted Answer · 2021-08-12 11:08:32Z

class Solution {
    public int[] duplicateZeros(int[] arr) {
        int n = arr.length;
        int count = 0;
        /* While we are not at the end of arr and the value is 0... */
        for(; (count < n) && (arr[count] == 0); count++) {
            /* Add one to count until we are done */
        }
        
        /* If half or more of the array is 0, then we zero things and are done */
        if (count > n/2) {
            for (int i = count; i < n; i++) {
                arr[i] = 0;
            }
            return arr;
        }

        /* We have shifting work to do :'( */
        int end = n - 1;
        int loc = n - 1 - count;
        int boundary = 2 * count;
        /* Shift from loc to end while we have not copied into a space that will be 0 */
        for(; end >= boundary; end--; loc--) {
            arr[end] = arr[loc];
        }
        
        /* Put a 0 into all the spots there should be a zero, ignoreing the places there is already a 0 */
        for (int i = count; i < boundary; i++) {
            arr[i] = 0;
        }
        /* Done! */
        return arr;
    }
}

I didn't test this code... but it should be very close to what you want. I think your issue is that you overcomplicated your code and tried to wrap your steps into if{} else{} logic you didn't need to.

You also tried to do duff's loop by setting two 0's at once.

Also, you don't need to return arr - when you return to the caling function, you will have modified the original array.

Adriaan Koster · Accepted Answer · 2021-08-12 11:16:34Z

0

The biggest problem is that you are trying to create the result into the same array. If there are any 0's, this won't fit.

Here is a slightly simpler solution requiring Java 8 or higher:

public static int[] duplicateZeros(int[] arr) {
    return Arrays.stream(arr)
        .flatMap(i -> i == 0 ? IntStream.of(i, i) : IntStream.of(i))
        .toArray();
}

answered Aug 12, 2021 at 11:16

Adriaan Koster

16.3k5 gold badges51 silver badges64 bronze badges

Collectives™ on Stack Overflow

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related