Python O(mn) Time, O(max(m,n)) space, straightforward solution


  • 0

    My solution is quite straight forward. Four lists memorize the corresponding line.

    class Solution(object):
        def longestLine(self, M):
            """
            :type M: List[List[int]]
            :rtype: int
            """
            if not M or not M[0]: return 0
            m, n = len(M), len(M[0])
            row, col, dia, anti_dia = [0]*m, [0]*n, [0]*(m+n-1), [0]*(m+n-1)
            curr_row, curr_col, curr_dia, curr_anti_dia = [0]*m, [0]*n, [0]*(m+n-1), [0]*(m+n-1)
    
            for i in range(m):
                for j in range(n):
                    if M[i][j] == 0:
                        curr_row[i] = 0
                        curr_col[j] = 0
                        curr_dia[i+j] = 0
                        curr_anti_dia[i-j+n-1] = 0
                    else:
                        curr_row[i] += 1
                        curr_col[j] += 1
                        curr_dia[i+j] += 1
                        curr_anti_dia[i-j+n-1] += 1
                        row[i] = max(row[i], curr_row[i])
                        col[j] = max(col[j], curr_col[j])
                        dia[i+j] = max(dia[i+j], curr_dia[i+j])
                        anti_dia[i-j+n-1] = max(anti_dia[i-j+n-1],curr_anti_dia[i-j+n-1])
    
            return max(max(row),max(col),max(dia),max(anti_dia))
    

Log in to reply
 

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