Write a function that returns the maximum quantity of non-zero elements between two zero elements-CodePudding

Given an array of integers I need to find the maximum quantity of non zero elements between two zero elements

For example: int[] arr = {1,2,0,2,3,4,5,0,1,2,3,4,5,6,7,8,8,0,1}

This should return 9. However, this returns 4:

static int solution(int[] arr) {
    int count = 0;
    int maxCount = 0;

    for (int i = 0; i < arr.length - 1; i  ) {
        if (arr[i] == 0 && i < arr.length - 2) {
            i  ;
            while (arr[i] != 0) {
                count  ;
                i  ;
            }
            maxCount = count;
        }
    }
    return maxCount;
}

UPD: For the case of {1,2,3,0,0,3,2,1}, function should return 0

CodePudding user response：

Some issues:

The inner loop may run i out of the array's range.
When you find the ending zero, your code does not take into account that this zero is also the start of a new group, and "misses" it.
count is never reset to zero, so it keeps increasing also when you get into a second "group"
maxCount is set unconditionally, yet it should only be updated if the new count is greater than the count you already got.
There is no provision for when there is no group at all. I would suggest to return -1 in that case, so to differentiate it from the case where there is a group of length 0. This -1 should then be the initial value of the counts.

Also:

It is strange that the outer loop condition is made more strict by the if condition at the top of your loop. So why not make that i< arr.length-2 the loop condition?

Here is a correction of your attempt:

static int solution(int[] arr){
    int count = -1; // Start with invalid count
    int maxCount = -1;

    for (int i = 0; i < arr.length - 2; i  ) { // Stricter loop condition
        if (arr[i] == 0) {
            count = 0; // Reset counter
            // Safety & Look ahead for zero
            while (i   1 < arr.length && arr[i   1] != 0) {
                count  ;
                i  ;
            }
            if (i   1 >= arr.length) break; // No ending zero found
            // Only update if improvement
            if (count > maxCount) maxCount = count;
        }
    }
    return maxCount;
}

You can however reduce the code a bit by using the outer loop to do the job of the inner loop:

static int solution(int[] arr){
    int count = -1; // Start with invalid count
    int maxCount = -1;

    for (int i = 0; i < arr.length; i  ) {
        if (arr[i] == 0) {
            if (count > maxCount) maxCount = count;
            count = 0; // Start of a potential new group
        } else if (count >= 0) { // Only when a zero was already encountered
            count  ;
        }
    }
    return maxCount;
}

CodePudding user response：

This code works for me

public static int count(int[] arr){
    int total = 0;
    int count = 0;
    for (int i = 0; i < arr.length-1; i  ) {
        count = 0;
        int j = i;
        while(arr[j] != 0){
            count  ;
            j  ;
        }
        i  = count;
        if(count > total){
            total = count;
        }
    }
    return total;
}

CodePudding user response：

You can solve this in a single pass:

use a counter, initialized to -∞.
read every element in turn.
if you see a zero, reset the counter to 0, otherwise increment it.
remember the largest value reached by the counter.

We refine the solution to implement the last statement:

use a counter, initialized to -∞, and a maximum, initialized to 0.
read every element in turn.
if you see a zero, update the maximum and reset the counter to 0, otherwise increment the counter.

In practice, as -∞ is not representable, but it suffices to take a value sufficiently negative that it cannot yield a positive count. For instance, minus the length of the list will do.

Here is the algorithm at work, showing the current element, the counter and the maximum:

Notes about the correctness:

The numbers before the first 0 do not count. This is ensured by the fact that the counter remains negative until the first zero, so that the maximum will remain null.

The numbers after the last 0 do not count. This is ensured by the fact that the maximum is only updated when seeing a zero.

Successive zeros with no intervening numbers do keep the count as 0 and do not influence the maximum.