# Java Concise O(n) Time O(1) Space

• ``````public int findMaxConsecutiveOnes(int[] nums) {
int maxConsecutive = 0, zeroLeft = 0, zeroRight = 0;
for (int i=0;i<nums.length;i++) {
zeroRight++;
if (nums[i] == 0) {
zeroLeft = zeroRight;
zeroRight = 0;
}
maxConsecutive = Math.max(maxConsecutive, zeroLeft+zeroRight);
}
return maxConsecutive;
}
``````

• zero right can be considered as 1 accumulated. If the gap between 1 and 1 is only 1(zero), zeroleft can be a temp storage to store how many 1 has been calculated, and then move on accumulate. But if there are 2 or more 0 gap, after the 1st 0, left will only be used to the flipped single 1.

• @gatechyy Thanks!

• Thank you for your solution, concise and powerful.

• @compton_scatter How did you even think of this ? I just want to know your thought process. This is amazing :)

• Amazing idea!

• I came up with a different idea. Use variable index to record the position of zero, and initiate the index to -1. Once we find a zero, refresh the count and store the new index. But yours are very impressive. Never thought this way before!

``````public class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0, count = 0, index = -1;
for(int i = 0;i< nums.length; i++){
if(nums[i] == 1){
count++;
}else{
count = i - index;
index = i;
}
max = Math.max(max,count);
}
return max;
}
}
``````

• Any 1/0 string with at least one trailing `0` can be seeing as repeating of a pattern: `a` ones followed by 1 zero. We denote such a pattern by `p(a)`. Eg:

``````p(1) =def= 10
p(3) =def= 1110
p(5) =def= 111110
p(0) =def= 0
``````

pay attention to the last one. Also note that, each occurrence of `0` signals the end of such a pattern.

And such a string `0011011100` can be seen as `p(0) + p(0) + p(2) + p(3) + p(0)`. Reminder, count a pattern at its trailing `0`.

In OP's solution, the two variables `zeroLeft` and `zeroRight` serve these purposes: for each iteration, or index `i`

• `zeroLeft`: the length of pattern that ends no later than `i`.
• `zeroRight`: the length of the run of `1` if `i` is in one. 0 otherwise.

Here is a trace for your convenience :

``````    0   0   1   1   0   1   1   1   0   0   1   1   1   1   0   //entry
0   1   1   1   1   3   3   3   3   4   1   1   1   1   1   5   //zeroLeft
0   0   0   1   2   0   1   2   3   0   0   1   2   3   4   0   //zeroRight
``````

So, at each `i` that is `1`, we consider `zeroLeft + zeroRight` because for an example like `110111`, we are considering `len(p(2)) + len(run(3))` (`run(3)` as 3 consecutive `1`s).

The code's logic:

``````For each index i:
if nums[i] is 0: calculate the length of the pattern that ends at nums[i] , and put it into zeroLeft. Reset zeroRight because we are no longer in a run;
if nums[i] is 1: increment zeroRight which records run length, and try to update max with (zeroLeft + zeroRight);
``````

Of course, OP wrote his code in another way, but I think that is the logic here. I solved this problem with a similar approach (considering the separating zeroes), but OP's code is way more elegant than mine.

Again, this is only my way of interpreting this program, and it's highly unlikely this is the thinking process of OP himself. The concept of a pattern is coined not necessarily. I do hope this will aid in the process of you finding your own way of interpretation.

• Based on @compton_scatter 's brilliant solution.

Slight modification, instead of calculating Max value in each step, can just calculate when we hit a 0, and then finally one last time, before returning.

``````public int findMaxConsecutiveOnes(int[] nums) {
int maxCons = 0;
int zeroIncluded = 0;
int count = 0;
for (int i = 0; i < nums.length; i++) {
count++;
if (nums[i] == 0) {
maxCons = Math.max(maxCons, zeroIncluded + count - 1);
zeroIncluded = count;
count = 0;
}
}
return Math.max(maxCons, zeroIncluded + count);
}
``````

Results in a slightly faster code.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.