We can separate the problem into two subproblems. The first subproblem is, given a 1 dimensional list of 0's and 1's, what is the longest chain of consecutive 1s? The second subproblem is to generate every line (row, column, diagonal, and anti-diagonal).
The first problem is common. We keep track of the number of 1's we've seen before. If we see a 1, we add to our count and update our answer. If we see a 0, we reset. Alternatively, we can also use
itertools.groupby. Straightforward code for the first part looks like this:
def score(line): ans = count = 0 for x in line: if x: count += 1 ans = max(ans, count) else: count = 0 return ans
The second part is more complex. We can try to manipulate indices of the grid, but there is a trick. Each element in the grid belongs to exactly 4 lines: the r-th row, c-th column, (r+c)-th diagonal, and (r-c)-th anti-diagonal. We scan from left to right, top to bottom, adding each element's value to it's respective 4 groups. As we visited in reading order, our lines will be appended to in that order, which is suitable for our purposes.
def longestLine(self, A): if not A: return 0 def score(line): return max(len(list(v)) if k else 0 for k, v in itertools.groupby(line)) groups = collections.defaultdict(list) for r, row in enumerate(A): for c, val in enumerate(row): groups[0, r] += [val] groups[1, c] += [val] groups[2, r+c] += [val] groups[3, r-c] += [val] return max(map(score, groups.itervalues()))