DEV Community

loading...

Day-4 Maximum Consecutive Ones

mridubhatnagar profile image Mridu Bhatnagar ・2 min read

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:
  1. Create a dictionary which would have a count of 1's.
  2. 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.
  3. 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.
  4. 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:
  1. Instead of a dictionary. Set can be used. As we are only concerned about the values.
  2. The complexity of storing a value in the dictionary is O(1).
  3. Complexity of D.values() is 0(1).

NOTE -

  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.
  2. Libraries are purposefully not used. Interest is more in improving problem-solving. Then on calling a built-in method.

Discussion

pic
Editor guide
Collapse
paddy3118 profile image
Paddy3118

"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

from itertools import groupby

def answer(lst):
    return len(max(tuple(g) for k, g in groupby(lst)
                            if k == 1))

print(answer([1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]))

Which returns 3.

Collapse
cod3kid profile image
Muameddo Sufeeru

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

Collapse
paddy3118 profile image
Paddy3118

Python is a multi paradigm language. A class with only one method is a code smell, try using a simpler function.

Collapse
mridubhatnagar profile image
Mridu Bhatnagar Author

This is the default code skeleton on leetcode. You can have a look at it if you want.

Collapse
paddy3118 profile image
Paddy3118

Ah, then you just need to remember that it is a code smell, it just makes maintenence worse.