# Python O(MN) solution. Simple explanation

• For each element we keep 4 counters -
[consec ones in that row Left to Right till that elem]
[consec ones in that col Top to Bottom till that elem]
[consec ones in that anti-diag TopRight to LeftBottom till that elem]
[consec ones in that diag TopLeft to BottomRight till that elem]
and iterate from 1st element to last element in the matrix once.

``````def longestLine(self, M):
if len(M)==0: return 0
m,n=len(M),len(M[0])
P=[[[0]*4 for _ in range(0,n)] for j in range(0,m)]
for r in range(0,m):
for c in range(0,n):
if c==0: P[r][c][0]=M[r][c]
else: P[r][c][0]= (P[r][c-1][0]+M[r][c])*M[r][c]

if r==0: P[r][c][1]=M[r][c]
else: P[r][c][1]= (P[r-1][c][1]+M[r][c])*M[r][c]

if r==0 or c==n-1: P[r][c][2]=M[r][c]
else: P[r][c][2]= (P[r-1][c+1][2]+M[r][c])*M[r][c]

if r==0 or c==0: P[r][c][3]=M[r][c]
else: P[r][c][3]= (P[r-1][c-1][3]+M[r][c])*M[r][c]

return max([P[i][j][k] for i in range(0,m) for j in range(0,n) for k in range(0,4)])
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.