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


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

  • 0
    N

    Could you please briefly explain your answer?


  • 7
    G

    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.


  • 0
    N

    @gatechyy Thanks!


  • 0
    H

    Thank you for your solution, concise and powerful.


  • 0
    D

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


  • 0
    Z

    Amazing idea!


  • 1
    F

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

  • 1

    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 1s).

    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.


Log in to reply
 

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