Searching for maximum path of zeroes in matrix

Question

Given an 10 x N matrix of 1's and 0s, such as:

1 1 1 1 1 1 1 1
1 1 0 1 1 0 0 1
0 0 0 1 1 0 0 1
0 0 0 1 1 0 0 0
1 0 0 0 0 1 0 0
1 0 1 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

notes:

• the zeroes in a column are always between two runs of consecutive 1s. for example, a column such as 1 1 1 0 1 0 1 1 1 1 is not permitted

• there must be at least a gap of one zero in each column, ie a column such as: 1 1 1 1 1 1 1 1 1 1 is not allowed

I want to find the longest consecutive streak of zeroes from left to right. In this case, that would be 4, which corresponds to the path starting in the second column of the 5th row from the top,

The second longest is 3 and there are 3 examples of that.

I'm a bit stumped on this, especially for very large N (~10M). I am looking for suggestions for the right approach/data structure to use or a similar problem and the algorithm used there. Another potential way to model the problem is to represent the problem using two lists:

L1 = [2, 2, 1, 4, 4, 1, 1, 3]
L2 = [6, 3, 5, 5, 5, 5, 5, 5]

but still not quite sure how to come up with an efficient solution

Answer 1

The solution using itertools.groupby(), sum() and max() functions:

import itertools

m = [
    [1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 0, 1, 1, 0, 0, 1],
    [0, 0, 0, 1, 1, 0, 0, 1],
    [0, 0, 0, 1, 1, 0, 0, 0],
    [1, 0, 0, 0, 0, 1, 0, 0],
    [1, 0, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1]
]

max_zero_len = max(sum(1 for z in g if z == 0) 
                   for l in m for k,g in itertools.groupby(l))

print(max_zero_len)

The output:

4

---

for l in m for k,g in itertools.groupby(l) - will generate a separate group for each consecutive sequences of 1 and 0 values for each nested list. (like [1,1], [0], [1,1], [0,0] ...)

sum(1 for z in g if z == 0) - considers only 0's sequences and counts its length using sum function

max(...) - gets the maximum length among zero(0) sequences