Day-4 Maximum Consecutive Ones

#python #challenge #beginners

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)

Paddy3118 • Apr 16 '20 • Edited

"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.

Muhamed Sufail • Aug 29 '20

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