This problem is a part of LeetCode's Introduction to Data Structure Arrays - 101. This section covers the theoretical concepts related to Arrays first. Followed by problems to solve.
Given a binary array, find the maximum number of consecutive 1s in this array.
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.
The input array will only contain 0 and 1.
The length of the input array is a positive integer and will not exceed 10,000
- Create a dictionary which would have a count of 1's.
- As the dictionary has both key, value. We keep incrementing the value of count corresponding to the key. As soon as a 0 is encountered no change is made to the dictionary. Instead, the variable count is again set to 0 and key is incremented by 1.
- Finally, we have a dictionary where the count of consecutive ones is the value. And, the key just represents the count of windows of consecutive ones.
- As the value of the maximum element is to be returned in the output. Sort the dictionary based on values in descending order. Return the 0th element.
class Solution: def findMaxConsecutiveOnes(self, nums: List[int]) -> int: key = 0 count = 0 D = dict() for x in nums: if x: D[key] = count + 1 count += 1 else: count = 0 key += 1 if len(D) > 0: return sorted(D.values(), reverse=True) else: return 0
- Instead of a dictionary. Set can be used. As we are only concerned about the values.
- The complexity of storing a value in the dictionary is O(1).
- Complexity of D.values() is 0(1).
- class structure is the default code skeleton on Leetcode. Putting a small function inside of a class is not what I intend to do otherwise.
- Libraries are purposefully not used. Interest is more in improving problem-solving. Then on calling a built-in method.