Find the maximum number of consecutive zeros in an array

Question

Question: To find the maximum number of consecutive zeros in a given array.

Example:

Input: \${1, 2, 0, 0, 2, 4, 0, 2, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 7, 0}\$

Output: "Maximum number of consecutive zeros : 6"

Here is what I've come up with:

public class ZeroSeriesLength {

    public static void main(String[] args) {

        int[] values = {1, 2, 0, 0, 2, 4, 0, 2, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 7, 0};

        int maxLength = 0;
        int tempLength = 0;

        for (int i = 0; i < values.length; i++) {

            if (values[i] == 0) {
                tempLength++;
            } else {
                tempLength = 0;
            }

            if (tempLength > maxLength) {
                maxLength = tempLength;
            }
        }

        System.out.println("Maximum number of consecutive zeros : " + maxLength);
    }
}

Is the logic correct? Or can it be done via a simple approach?

Answer 1

Just a few short comments on your code:

Separation of concerns:

You should separate functionality into different parts. Currently your main method does everything. For small applications like this, that may not be a problem, but as soon as you have larger applications, it becomes more and more unpractical.

You should thus extract your "logic" into a method:

private static int countSuccessiveZeros(int[] values) {
   int maxLength = 0;
   int tempLength = 0;
   //....
   // Looping here
   return maxLength;
}

Now if you wanted to not count zeros, but twos, you could simply modify the code to the following:

private static int countSuccessive(int[] values, int target) {
   int maxLength = 0;
   int tempLength = 0;
   //Your loop here, instead of 0 use target to compare
   return maxLength;
}

This also makes your main-method more readable:

public static void main(String[] args) {
   int[] values = {1, 2, 0, 0, 2, 4, 0, 2, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 7, 0};
   int successiveZeros = countSuccessive(values, 0);
   System.out.println("Maximum number of consecutive zeros : " + successiveZeros);
}

Naming:

Very nice, a compliment. Your variable names are short, clear, descriptive and follow Java conventions (camelCase). Keep it up ;)

Answer 2

Keeping in mind of @Vogel612's nice answer (which is completly true), I have 2 more points to make.

A for-each loop is easier than a normal for loop. Don't worry about the correct order, it's the same as the order you have in the "standard" for loop.

Secondly, I would move the if (values[i] == 0) to a ternary statement. You have an if-else statement that sets the same integer.

The second if statement is in my opinion great. Simple check and if true set the value.

So my solution is:

 public static int countSuccessiveb (int[] values, int target) {
    int maxLength = 0;
    int tempLength = 0;

    for (int value : values) {
        tempLength = (value == target) ? 1 + tempLength : 0;
        if (tempLength > maxLength) {
            maxLength = tempLength;
        }
    }
    return maxLength;
}

Answer 3

In the addendum to aforesaid :

1 . The comparation (tempLength > maxLength) should be moved to the first if block. If current is not zero, then tempLength is obviously not greater than maxLength, and therefore comparation is useless waste of CPU time.

       if (values[i] == 0) {
          if (++tempLength > maxLength) {
                maxLength = tempLength;
          }

       } else {
                tempLength = 0;
       }

2 . The comparation and assignment of maxLength could be reduced to:

maxLength = tempLength > maxLength?tempLength : maxLength; 

//or

maxLength = Math.max(maxLength,tempLength); 

3 . Inline incrementation of tempLength :

maxLength = Math.max(maxLength,++tempLength); 

So you code may look just like:

    public class ZeroSeriesLength {
      public static void main(String[] args) {
        int[] values = {1, 2, 0, 0, 2, 4, 0, 2, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 7, 0};

        int maxLength = 0;
        int tempLength = 0;

        for (int i = 0; i < values.length; i++) {

            if (values[i] == 0) {
                maxLength = Math.max(maxLength, ++tempLength);
            } else {
                tempLength = 0;
            }
        }

        System.out.println("Maximum number of consecutive zeros : " + maxLength);
    }
}

Answer 4

Why count every time all zero? Just look if this index is the first zero, then check if index + max_zero_strike + 1 == 0. If true, check the value before and after. That way you may be a bit more efficient.

big edit: trying to make the code work, i've found out this solution, that drift a lot form original code, but not so much from original concept, and also it is a lot clearer.

new (working) code:

private static int getMax(int[] values) {
    int maxLength = 0;
    for (int i = 0; i < values.length; i+=1+maxLength) { // here we are looking for the first zero. if lenght remaining is lesser than actual max zero-strike, no way we caund found a better.

        if (values[i] == 0) { // is zero

            //find leftmost zero
            int tmpLeft = 0;
            while(tmpLeft < i && values[i-tmpLeft-1] == 0){
                tmpLeft++;
            }

            //find righmost zero
            int tmpRight = 0;
            while(tmpRight+i < values.length && values[i+tmpRight] == 0){
                tmpRight++;
            }

            maxLength = Math.max(maxLength, tmpLeft+tmpRight);



        }
    }

    return maxLength;
}

Also runned some benchmark versus OP code (random sample of value generated with values[a] = r.nextInt(3); ). (banchamrk full code: https://gist.github.com/MauroMombelli/b68641a785f3e93fd410)

for array of size == 10, op code is 2 time faster on this pc (1000 nanosec vs 2000 nanosec)

for array of size == 100 code execution are similar

for array == 1000 my code is faster, op code take fixed 5700 nanosec, my code from 3000 to 3500

for array == 1000, but value from 0 to 9, op code take fixed 3079nanosec, my code from 2200 to 2600

for array == 1000 (0-9) op code take 30.000-47.000 mine 10.000-13.000

old (not working) code:

public class ZeroSeriesLength {

    public static void main(String[] args) {

        int[] values = {1, 2, 0, 0, 2, 4, 0, 2, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 7, 0};

        int maxLength = 0;

        for (int i = 0; i < values.length-maxLength ; i++) { //here we are looking for the first zero. if lenght remaining is lesser than actual max zero-strike, no way we caund found a better.

            if (values[i] == 0) { //first zero
                int tmpCheck = i+maxLength+1;//shot for a streak with at least one more zero
                while (tmpCheck > i && values[tmpCheck] == 0){
                    tmpCheck--;
                }
                if (tmpCheck == i){ //true if those between i and i+maxLength+1 was all zero!
                    //we have a strike bigger than actual by at least 1!
                    maxLength++;
                    //now check for additional zero on the right, but please don't overflow
                    while(i + maxLength + 1 < values.length && values[i+maxLength+1] == 0){
                        maxLength++;
                    }
                }
                i+=maxLength+1; //no need to check again all that zero and last not-zero!
            }
        }

        System.out.println("Maximum number of consecutive zeros : " + maxLength);
    }
}

Answer 5

I have thought of this:

public static int countSuccessive2(int[] values, int target) {
    int maxLength = 0;
    int tempLength = 0;

    for (int i = 0; i < values.length; i++) {

        if (values[i] == target) {
            tempLength++;
        } else {
            tempLength = 0;

            if(values.length - i <= maxLength){
                break;
            }
        }

        if (tempLength > maxLength) {
            maxLength = tempLength;
        }
    }

    return maxLength;
}

What I do above is: if I've just broken a chain and I already have a chain of, let's say, 5 zeroes, and my array has only 4 positions left to check, why check them? I can't get a bigger chain.

Maybe this time, with this little array of values, it doesn't matter, but in a bigger one with chains that have hundreds of target elements, it would matter.

What do you think?