# Find the maximum number of consecutive zeros in an array

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?

• Suggestion, put if (tempLength > maxLength) { maxLength = tempLength; } in the else statement. May 13, 2014 at 7:08
• @NPSF3000 I think that would be rather premature optimization... It doesn't give much with a reasonable amount of Items and a good branch-prediction algorithm. May 13, 2014 at 7:11
• @Vogel612 True, and if you don't put another one after the loop you could miss the last length. May 13, 2014 at 7:36
• You could put it right after tempLength++. It's probably fine where it is though. May 13, 2014 at 10:14
• Algorithm is absolutely fine. Quite straightforward, easy to see that it is correct, performance close to optimal. Unless you have evidence that its performance is critical, it can stay as it is. You'd probably want to turn the algorithm into a function for reuse. Looking at the comments above, you see how trying to optimise speed can lead to subtle problems if you don't watch out. May 13, 2014 at 21:56

### 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;
return maxLength;
}


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

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

• tempLength = ++tempLength is weird, since the ++ operator already performs an assignment. It takes me a minute to convince myself that it works. May 13, 2014 at 16:36
• @200_success but it works or not :) May 13, 2014 at 16:48
• It works, but tempLength = (value == target) ? 1 + tempLength : 0 would have been better. Same number of symbols, ignoring whitespace. May 13, 2014 at 16:57
• @chillworld The original code works as well. The point of code review to produce better code. FYI, I would put some whitespace in that ternary. Probably a newline after the ?, and after the : such that tempLength and 0 line up. May 13, 2014 at 17:06
• @200_success your right, I'll edit it May 13, 2014 at 17:15

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

• I think the inline incrementation of tempLength is difficult to spot and thus maybe a little problematic... Either way, nice point on the if-statement +1 May 13, 2014 at 8:19
• The logic is certainly cleaner this way. However, with Math.max(), I wouldn't claim that it saves CPU cycles. May 13, 2014 at 16:41
• I don't think you will win (much) by refactoring the if-statement to the Math.Max May 13, 2014 at 19:56

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

• Nice idea, but I'm not convinced that the optimization is worth the complexity of iterating out of order. values = { 0 }ArrayIndexOutOfBoundsException. values = { 0, 0 } → 1. May 13, 2014 at 16:52
• Code is untested, i may fix it later, buf the important is you get the idea. Optimization depends on need May 13, 2014 at 17:06
• If you can produce evidence that this performs > 15% faster on average I will upvote May 13, 2014 at 17:16
• challenge accepted, I'll try at home May 13, 2014 at 17:20
• @lesto small overheads can be big overheads if part of a much larger algorithm. I agree with you in general though. It's just always good to have consideration for possible data. May 14, 2014 at 14:38

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?