Longest Line Of Consecutive One In Matrix - Leetcode Solution

Problem Statement

Given a binary matrix matrix, find the maximum length of a line of consecutive ones in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.

Example Input:

matrix = [[0,1,1,0],
          [0,1,1,0],
          [0,0,0,1]]

Output:

4

Explanation: The longest line of consecutive 1s is horizontal in the first row, counting from the second column to the third column.

Solution

We can solve this problem using dynamic programming and four different arrays. Let's break down the solution step-by-step:

1. Initialize four arrays horizontal, vertical, diagonal and anti_diagonal of the same size as the matrix with all values initialized to 0. These arrays store the maximum length of a line of consecutive ones ending at each position (i,j) of the matrix in four different directions.

2. Loop through each cell (i,j) of the matrix and update these four arrays. We compute the values for all the four arrays at each iteration.

• For the horizontal array, if matrix[i][j] == 1, then horizontal[i][j] = horizontal[i][j-1] + 1, else horizontal[i][j] = 0.

• For the vertical array, if matrix[i][j] == 1, then vertical[i][j] = vertical[i-1][j] + 1, else vertical[i][j] = 0.

• For the diagonal array, if matrix[i][j] == 1, then diagonal[i][j] = diagonal[i-1][j-1] + 1, else diagonal[i][j] = 0.

• For the anti_diagonal array, if matrix[i][j] == 1, then anti_diagonal[i][j] = anti_diagonal[i-1][j+1] + 1, else anti_diagonal[i][j] = 0.

3. Loop through each cell (i,j) of the matrix again and find the maximum value in all the four arrays. Return the maximum value as the answer.

Here is the implementation of the above solution in Python:

def longestLine(matrix):
    if not matrix:
        return 0
    
    m, n = len(matrix), len(matrix[0])
    horizontal, vertical, diagonal, anti_diagonal = [[0]*n for _ in range(m)], [[0]*n for _ in range(m)], [[0]*n for _ in range(m)], [[0]*n for _ in range(m)]
    max_length = 0
    
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 1:
                if j > 0:
                    horizontal[i][j] = horizontal[i][j-1] + 1
                else:
                    horizontal[i][j] = 1
                    
                if i > 0:
                    vertical[i][j] = vertical[i-1][j] + 1
                else:
                    vertical[i][j] = 1
                    
                if i > 0 and j > 0:
                    diagonal[i][j] = diagonal[i-1][j-1] + 1
                else:
                    diagonal[i][j] = 1
                    
                if i > 0 and j < n-1:
                    anti_diagonal[i][j] = anti_diagonal[i-1][j+1] + 1
                else:
                    anti_diagonal[i][j] = 1
                    
                # Update the maximum length
                max_length = max(max_length, horizontal[i][j], vertical[i][j], diagonal[i][j], anti_diagonal[i][j])
                    
    return max_length

Time Complexity: O(mn), where m and n are the dimensions of the matrix. Space Complexity: O(mn), we are maintaining four 2D arrays with the same dimensions as the matrix.

1