Python O(MN) solution. Simple explanation


  • 0

    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)])
    

Log in to reply
 

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