Max Consecutive Ones

Question

I am practicing two pointers techniques to solve Max Consecutive Ones - LeetCode

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
 The maximum number of consecutive 1s is 3.
Note:

The input array will only contain 0 and 1.

The length of input array is a positive integer and will not exceed 10,000

The solution use Kadane algorithms

class Solution:
    def findMaxConsecutiveOnes(self, nums: "List[int]") -> int:

        loc_max = glo_max = 0
        for i in range(len(nums)):
            if nums[i] == 1: 
                loc_max += 1
            elif nums[i] != 1:
                glo_max = max(glo_max, loc_max)
                loc_max = 0  
        #in case of the corner case [.....,1 ,1, 1]         
        return max(glo_max, loc_max)

The problem with the solution is that it's not a decent two pointers solution with slow and fast pointer.(It did not an explicit slow pointer)

A intuitive idea to employ slow pointer is to take a slow pointer to remember the starting index of consecutive ones, when fast pointer reach a non-one, the relation is length= fast - slow.

However, it is difficult to locate slow pointing to a first One. [0, 0, 0, 1, 1, 1, 1],

As a comprised proposal, re-define slow to the forward non-One of a ones array,when fast reach to another non-One. Use relation: length = fast -slow + 1

class Solution:
    def findMaxConsecutiveOnes(self, nums: "List[int]") -> int:
        """
        #1Sort####
        ##2Strategy######
        CP: two pointers
        RU: res  = fast - slow 
        """
       ###3Solve######
        slow, fast, glo_max = 0, 0, 0
        for fast in range(len(nums)):
            if nums[fast] != 1: #stop
                loc_max = fast -slow + 1
                glo_max = max(glo_max, loc_max)
                slow = fast 
        return max(loc_max, glo_max)
        ####4Check#########################
        #[0, 0,1, 0, 1, 1]

I tried and debugged multiple times to define slow as the first index of Ones sub-array, did not get the desired result.

Could you please give any hints for that solution.

score 5 · Accepted Answer · answered Apr 20 '19 at 09:24

I think you are pretty close, it's just a matter of really watching when the indexes get updated relative you where you calculate the length. And there are some tricky cases like [1] that will fail if it's not correct.

I find it easier to do this with a while loop so I can be explicit about where the indexes are updated. Here's one way that works:

 def findMaxConsecutiveOnes(nums):
        slow, fast, glo_max, loc_max = 0, 0, 0, 0
        while fast < len(nums):
            if nums[fast] == 0:
                loc_max = fast - slow  
                glo_max = max(glo_max, loc_max)
                slow = fast + 1      # need to add one more because we haven't incremented fast yet

            fast += 1
        loc_max = fast - slow        # end check for cases that end with 1
        return max(loc_max, glo_max)

findMaxConsecutiveOnes([1])    # 1 
findMaxConsecutiveOnes([1, 1]) # 2
findMaxConsecutiveOnes([0, 1]) # 1
findMaxConsecutiveOnes([0, 1, 1, 0, 0, 1, 1, 1, 0]) # 3

This passes the leet code test, but doesn't set any speed records.

score 1 · Answer 2 · answered Jun 21 '21 at 15:22

u can try the below solution. Basically u keep a track of count until u hit 0 and then return the maxCount.

  public int findMaxConsecutiveOnes(int[] nums) {
    int currentCount=0;
    int maxCount = 0;
    for(int i=0;i<nums.length;i++){
        if(nums[i]==1){
            currentCount++;
            if(currentCount>maxCount){
                maxCount=currentCount;
            }
        }
        else{
            currentCount=0;
        }

    }
    return maxCount;
}

score 0 · Answer 3 · answered Jun 29 '21 at 10:04

0

You can also solve this program like below (1 line solution) :

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        return len(max("".join(map(str, nums)).split("0")))

May this solution help you :)

answered Jun 29 '21 at 10:04

sourab maity

1,025
2
8
16

score 0 · Answer 4 · answered Mar 09 '23 at 05:13

This is how i solved this:

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        c = 0
        r = 0
        for i,v in enumerate(nums):
            if v == 0:
                c = 0
            else:
                c +=1
                r = max(r,c)
        return r

Here is my time and space analysis results:

Max Consecutive Ones

4 Answers4

Linked