Python solution with detailed explanation


  • 0
    G

    Solution

    Max Consecutive Ones II https://leetcode.com/problems/max-consecutive-ones-ii/

    Algorithm 1: O(N) time and space

    • Use 0 as a marker and store streaks around a 0 in runs array.
    • Then compare adjacent sums + 1 and return the maximum such sum. 1 is added for the zero that will be flipped.
    class Solution(object):
        def findMaxConsecutiveOnes(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            runs, cnt = [], 0
            for x in nums:
                if x == 1:
                    cnt += 1
                else:
                    runs.append(cnt)
                    cnt = 0
            runs.append(cnt)
            max_len = runs[0]
            for i in range(1, len(runs)):
                max_len = max(max_len,runs[i]+runs[i-1]+1)
            return max_len
    

    Algorithm 2: O(N) time and O(1) space

    class Solution(object):
        def findMaxConsecutiveOnes(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            prev, curr, max_len = 0, 0, 0
            for x in nums:
                if x == 1:
                    curr = curr + 1
                else:
                    max_len, prev = max(max_len, prev+curr+1), curr
                    curr = 0
            if curr == len(nums): #[1,1,1,1]
                return curr
            elif nums[-1] == 1: # Must have been atleast a zero somewhere
                return max(max_len, prev+curr+1)
            return max_len
    

Log in to reply
 

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