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. –  NPSF3000 May 13 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. –  Vogel612 May 13 at 7:11
@Vogel612 True, and if you don't put another one after the loop you could miss the last length. –  NPSF3000 May 13 at 7:36
You could put it right after tempLength++. It's probably fine where it is though. –  tfinniga May 13 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. –  gnasher729 May 13 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. –  200_success May 13 at 16:36
@200_success but it works or not :) –  chillworld May 13 at 16:48
It works, but tempLength = (value == target) ? 1 + tempLength : 0 would have been better. Same number of symbols, ignoring whitespace. –  200_success May 13 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. –  Cruncher May 13 at 17:06
@200_success your right, I'll edit it –  chillworld May 13 at 17:15

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. –  200_success May 13 at 16:52
Code is untested, i may fix it later, buf the important is you get the idea. Optimization depends on need –  lesto May 13 at 17:06
If you can produce evidence that this performs > 15% faster on average I will upvote –  Cruncher May 13 at 17:16
challenge accepted, I'll try at home –  lesto May 13 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. –  Cruncher May 14 at 14:38

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 –  Vogel612 May 13 at 8:19
The logic is certainly cleaner this way. However, with Math.max(), I wouldn't claim that it saves CPU cycles. –  200_success May 13 at 16:41
I don't think you will win (much) by refactoring the if-statement to the Math.Max –  GroundZero May 13 at 19:56

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?

-

I'm no Java programmer, but this is a simple example of Run-Length Encoding. Here is the R code for anyone who could translate into Java. All you have to do is skim the "values" output for zero and find the maximum "length" value which corresponds.

EDIT: My intent here was not to jump languages, but to point out that the basic concept of Run-Length Encoders (a well-known operation in the world of communications and data compression) is IMHO a better approach to solving the actual problem at hand. It is, beyond argument, better to solve the problem than to solve the code snippet in question.

So, here's the pseudocode sequence I would recommend coding up.

rle.out =  RLE(your_data)
# rle.out contains two vectors: the repetition lengths and the actual data values for each rep
zero_locs = FIND(rle.out@values == 0 )
long_string = MAX(rle.out@lengths[zero_locs])  #I used "[ ]" to indicate indices


Example in the R-language provided as a simple reference.

function (x)
{
if (!is.vector(x) && !is.list(x))
stop("'x' must be a vector of an atomic type")
n <- length(x)
if (n == 0L)
return(structure(list(lengths = integer(), values = x),
class = "rle"))
y <- x[-1L] != x[-n]
i <- c(which(y | is.na(y)), n)
structure(list(lengths = diff(c(0L, i)), values = x[i]),
class = "rle")
}

-
Greetings, you got down voted because 1) You are supposed to review the code, you did not. 2) Optionally counter propose code in the same language, you picked another language 3) Your counter proposal code is not a functional equivalent of the poster code ( not even close ). –  konijn May 13 at 16:11
@konijn I'm not really surprised either. Maybe I just should have written "Hey what you want is an RLE calculator and the heck with your naive approach!" But I take exception to your #3 point. The point of my answer is that using RLE is, I believe, a better approach to begin with. –  Carl Witthoft May 13 at 16:43
I think what you're trying to say is, the problem can be decomposed into some high-level operations: RLE → find zero values → max, and the code could be more expressive if you took advantage of that. That may be true, but not necessarily a good answer in this context. Your frustration comes from the fact that Java is not R, and your suggestion is neither natural nor idiomatic for Java. –  200_success May 13 at 17:27
@CarlWitthoft You can take exception if you wish, but where is the equivalent of System.out.println("Maximum number of consecutive zeros : " + maxLength); –  konijn May 13 at 18:00
@CarlWitthoft I believe that questioning the OP's choice of language won't lead anywhere. There can be hundreds of reasons why Java was chosen: Platform compability (what if this algorithm is intended to be used inside an Android application?), previous knowledge of the language, etc. My point is: There's always reasons for why a language is chosen. –  Simon André Forsberg May 13 at 19:09