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.
Problem Statement
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.
Note:
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
Solution Approach:
- 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)[0]
else:
return 0
Learnings:
- 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).
NOTE -
- 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.
Top comments (5)
"find the length of the maximum runs/groups of ones in a list"
Groups means check groupby for me and I came up with the following
Which returns 3.
a = [0,1, 0,1, 1, 1, 0, 1, 1]
streak = 0
count = 0
for (i in a) {
if (a[i] == 1) {
count++;
streak = Math.max(streak, count)
}
else {
count = 0
}
}
console.log(streak)
This works too.. But its in JS
Python is a multi paradigm language. A class with only one method is a code smell, try using a simpler function.
This is the default code skeleton on leetcode. You can have a look at it if you want.
Ah, then you just need to remember that it is a code smell, it just makes maintenence worse.