Problem Description

You are given a binary matrix mat of size m x n (where each element is either 0 or 1). Your task is to find the length of the longest line of consecutive 1s in the matrix. A line can be in any of the following four directions:

• Horizontal (left to right in a row)
• Vertical (top to bottom in a column)
• Diagonal (top-left to bottom-right)
• Anti-diagonal (top-right to bottom-left)

Thought Process

At first glance, this problem seems to require checking every possible line in the matrix. A brute-force approach would involve scanning every starting cell and extending lines in all four directions, counting consecutive 1s. However, this would be inefficient, especially for large matrices, as it would repeat work and potentially check the same lines multiple times.

To optimize, we can use dynamic programming. The key insight is that for each cell containing a 1, the length of the line ending at that cell in any direction depends only on the previous cell in that direction. By keeping track of the lengths of lines ending at each cell for all four directions, we can compute the result efficiently in a single pass.

Solution Approach

We will use dynamic programming to track the length of consecutive 1s ending at each cell in each direction. Here's how we can do it:

1. Initialize a 3D DP array:
   • Let dp[i][j][k] represent the length of the line of 1s ending at cell (i, j) in direction k.
   • Directions: 0 = horizontal, 1 = vertical, 2 = diagonal, 3 = anti-diagonal.
2. Iterate through the matrix:
   • For each cell (i, j) that contains a 1, update all four directions:
   • Horizontal: dp[i][j][0] = dp[i][j-1][0] + 1 if j > 0
   • Vertical: dp[i][j][1] = dp[i-1][j][1] + 1 if i > 0
   • Diagonal: dp[i][j][2] = dp[i-1][j-1][2] + 1 if i > 0 and j > 0
   • Anti-diagonal: dp[i][j][3] = dp[i-1][j+1][3] + 1 if i > 0 and j < n-1
   • If out of bounds, start with 1.
3. Keep track of the global maximum:
   • After updating each direction, update the result if the current length is greater than the previous maximum.
4. Return the maximum length found.

This approach ensures we only do a constant amount of work per cell, leading to an efficient solution.

Example Walkthrough

Consider the following matrix:

    mat = [
      [0,1,1,0],
      [0,1,1,0],
      [0,0,0,1]
    ]
  

Let's trace the computation:

• Start at (0,1): horizontal and vertical are both 1, diagonal and anti-diagonal are 1.
• At (0,2): horizontal is 2 (since (0,1) is 1), vertical is 1, diagonal is 1, anti-diagonal is 1.
• At (1,1): vertical is 2 (from (0,1)), horizontal is 1, diagonal is 1, anti-diagonal is 1.
• At (1,2): vertical is 2 (from (0,2)), horizontal is 2 (from (1,1)), diagonal is 2 (from (0,1)), anti-diagonal is 1.
• At (2,3): only cell with 1 in this row, so all directions are 1 except anti-diagonal, which is 3 (from (1,2)).

The longest line is in the anti-diagonal direction, length 3 (from (2,3) up to (0,1)).

Time and Space Complexity

Brute-force:

• For each cell, scan all four directions up to the edge of the matrix. For an m x n matrix, this is O(mn(m+n)) in the worst case.

• We visit each cell once, and for each cell, we update four values (one per direction): O(mn) time.
• Space: O(mn) for the DP array (can be reduced to O(n) with rolling arrays if needed).

Thus, the optimized approach is efficient and suitable for large matrices.

Summary

The problem of finding the longest consecutive line of 1s in a binary matrix across all four directions can be solved efficiently using dynamic programming. By maintaining the length of lines ending at each cell for every direction, we avoid redundant work and achieve a linear-time solution relative to the matrix size. This approach is both elegant and practical, leveraging the overlapping subproblems inherent in the matrix structure.

Code Implementation

class Solution:
    def longestLine(self, mat):
        if not mat or not mat[0]:
            return 0
        m, n = len(mat), len(mat[0])
        # dp[i][j][k]: 0=horizontal, 1=vertical, 2=diagonal, 3=anti-diagonal
        dp = [[[0]*4 for _ in range(n)] for _ in range(m)]
        res = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    # Horizontal
                    dp[i][j][0] = dp[i][j-1][0]+1 if j>0 else 1
                    # Vertical
                    dp[i][j][1] = dp[i-1][j][1]+1 if i>0 else 1
                    # Diagonal
                    dp[i][j][2] = dp[i-1][j-1][2]+1 if i>0 and j>0 else 1
                    # Anti-diagonal
                    dp[i][j][3] = dp[i-1][j+1][3]+1 if i>0 and j<n-1 else 1
                    res = max(res, max(dp[i][j]))
        return res
      

class Solution {
public:
    int longestLine(vector<vector<int>>& mat) {
        if (mat.empty() || mat[0].empty()) return 0;
        int m = mat.size(), n = mat[0].size(), res = 0;
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(4, 0)));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 1) {
                    // Horizontal
                    dp[i][j][0] = (j > 0 ? dp[i][j-1][0] : 0) + 1;
                    // Vertical
                    dp[i][j][1] = (i > 0 ? dp[i-1][j][1] : 0) + 1;
                    // Diagonal
                    dp[i][j][2] = (i > 0 && j > 0 ? dp[i-1][j-1][2] : 0) + 1;
                    // Anti-diagonal
                    dp[i][j][3] = (i > 0 && j < n-1 ? dp[i-1][j+1][3] : 0) + 1;
                    res = max(res, max({dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3]}));
                }
            }
        }
        return res;
    }
};
      

class Solution {
    public int longestLine(int[][] mat) {
        if (mat == null || mat.length == 0 || mat[0].length == 0) return 0;
        int m = mat.length, n = mat[0].length, res = 0;
        int[][][] dp = new int[m][n][4];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 1) {
                    // Horizontal
                    dp[i][j][0] = (j > 0 ? dp[i][j-1][0] : 0) + 1;
                    // Vertical
                    dp[i][j][1] = (i > 0 ? dp[i-1][j][1] : 0) + 1;
                    // Diagonal
                    dp[i][j][2] = (i > 0 && j > 0 ? dp[i-1][j-1][2] : 0) + 1;
                    // Anti-diagonal
                    dp[i][j][3] = (i > 0 && j < n-1 ? dp[i-1][j+1][3] : 0) + 1;
                    res = Math.max(res, Math.max(Math.max(dp[i][j][0], dp[i][j][1]), 
                            Math.max(dp[i][j][2], dp[i][j][3])));
                }
            }
        }
        return res;
    }
}
      

var longestLine = function(mat) {
    if (!mat || mat.length === 0 || mat[0].length === 0) return 0;
    const m = mat.length, n = mat[0].length;
    // dp[i][j][k]: 0=horizontal, 1=vertical, 2=diagonal, 3=anti-diagonal
    const dp = Array.from({length: m}, () => Array.from({length: n}, () => [0,0,0,0]));
    let res = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (mat[i][j] === 1) {
                // Horizontal
                dp[i][j][0] = (j > 0 ? dp[i][j-1][0] : 0) + 1;
                // Vertical
                dp[i][j][1] = (i > 0 ? dp[i-1][j][1] : 0) + 1;
                // Diagonal
                dp[i][j][2] = (i > 0 && j > 0 ? dp[i-1][j-1][2] : 0) + 1;
                // Anti-diagonal
                dp[i][j][3] = (i > 0 && j < n-1 ? dp[i-1][j+1][3] : 0) + 1;
                res = Math.max(res, Math.max(...dp[i][j]));
            }
        }
    }
    return res;
};