LeetCode: Max Consecutive Ones Posted on January 20, 2018July 26, 2020 by braindenny Max Consecutive Ones Similar Problems: LeetCode: Max Consecutive Ones LeetCode: Max Consecutive Ones II LeetCode: Max Consecutive Ones III LeetCode: Minimum Swaps to Group All 1’s Together CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #array 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 Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. class Solution(object): ## https://code.dennyzhang.com/max-consecutive-ones ## Basic Ideas: counter ## If found one 0, reset the counter to 0. Otherwise counter + 1 ## ## Complexity: Time O(n), Space O(1) def findMaxConsecutiveOnes(self, nums): """ :type nums: List[int] :rtype: int """ max_count, counter = 0, 0 for num in nums: if num == 1: counter = counter+1 max_count = max(max_count, counter) else: counter = 0 return max_count ## Ideas: Two pointers ## i points to the start of consecutive of 1s ## j points to the next element of the end of consecutive of 1s. ## ## Assumption: [1, 0, 1], we should return 1 ## Complexity: Time O(n), Space O(1) def findMaxConsecutiveOnes_v1(self, nums): """ :type nums: List[int] :rtype: int """ max_count = 0 length = len(nums) i = 0 while i < length: if nums[i] == 0: i += 1 continue # nums[i] == 1 j = i + 1 while j < length and nums[j] == 1: j += 1 # nums[j] == 0 and nums[j-1] == 1 max_count = max(max_count, j-i) # move to next i = j + 1 return max_count # s = Solution() # print s.findMaxConsecutiveOnes([0]) # 0 # print s.findMaxConsecutiveOnes([1, 0, 1]) # 1 # print s.findMaxConsecutiveOnes([1]) # 1 Post Views: 3