485. Max Consecutive Ones - Explanation

Description

You are given a binary array nums, return the maximum number of consecutive 1's in the array.

Example 1:

Input: nums = [1,1,0,1,1,1]

Output: 3

Example 2:

Input: nums = [1,0,1,1,0,1]

Output: 2

Constraints:

1 <= nums.length <= 100,000
nums[i] is either 0 or 1.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        n, res = len(nums), 0

        for i in range(n):
            cnt = 0
            for j in range(i, n):
                if nums[j] == 0: break
                cnt += 1
            res = max(res, cnt)
        
        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Iteration - I

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        res = cnt = 0
        for num in nums:
            if num == 0:
                res = max(res, cnt)
                cnt = 0
            else:
                cnt += 1

        return max(cnt, res)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

3. Iteration - II

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        res = cnt = 0
        for num in nums:
            cnt += 1 if num else -cnt
            res = max(res, cnt)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$