Problem

Given an m x n binary matrix mat, return the length of the longest line of consecutive one in the matrix.

The line could be horizontal, vertical, diagonal, or anti-diagonal.

Examples

Example 1:

1
2
3

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/0500-0599/0562.Longest%20Line%20of%20Consecutive%20One%20in%20Matrix/images/long1-grid.jpg)
Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

Example 2:

1
2
3

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/0500-0599/0562.Longest%20Line%20of%20Consecutive%20One%20in%20Matrix/images/long2-grid.jpg)
Input: mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]
Output: 4

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 10^4
  • 1 <= m * n <= 10^4
  • mat[i][j] is either 0 or 1.

Solution

Method 1 – Dynamic Programming for All Directions (1)

Intuition

To find the longest line of consecutive ones in all four directions (horizontal, vertical, diagonal, anti-diagonal), we use dynamic programming to keep track of the length of consecutive ones ending at each cell for each direction.

Approach

  1. Initialize a 3D dp array where dp[i][j][d] stores the length of consecutive ones ending at cell (i, j) in direction d (0: horizontal, 1: vertical, 2: diagonal, 3: anti-diagonal).
  2. For each cell in the matrix:
    • If the cell is 1, update dp for all four directions based on previous cells.
    • Update the answer with the maximum value found.
  3. Return the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int longestLine(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size(), ans = 0;
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(4)));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 1) {
                    dp[i][j][0] = (j > 0 ? dp[i][j-1][0] : 0) + 1; // horizontal
                    dp[i][j][1] = (i > 0 ? dp[i-1][j][1] : 0) + 1; // vertical
                    dp[i][j][2] = (i > 0 && j > 0 ? dp[i-1][j-1][2] : 0) + 1; // diagonal
                    dp[i][j][3] = (i > 0 && j+1 < n ? dp[i-1][j+1][3] : 0) + 1; // anti-diagonal
                    ans = max({ans, dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3]});
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

func longestLine(mat [][]int) int {
    m, n := len(mat), len(mat[0])
    dp := make([][][]int, m)
    for i := range dp {
        dp[i] = make([][]int, n)
        for j := range dp[i] {
            dp[i][j] = make([]int, 4)
        }
    }
    ans := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if mat[i][j] == 1 {
                dp[i][j][0] = 1
                if j > 0 {
                    dp[i][j][0] += dp[i][j-1][0]
                }
                dp[i][j][1] = 1
                if i > 0 {
                    dp[i][j][1] += dp[i-1][j][1]
                }
                dp[i][j][2] = 1
                if i > 0 && j > 0 {
                    dp[i][j][2] += dp[i-1][j-1][2]
                }
                dp[i][j][3] = 1
                if i > 0 && j+1 < n {
                    dp[i][j][3] += dp[i-1][j+1][3]
                }
                for d := 0; d < 4; d++ {
                    if dp[i][j][d] > ans {
                        ans = dp[i][j][d]
                    }
                }
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int longestLine(int[][] mat) {
        int m = mat.length, n = mat[0].length, ans = 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) {
                    dp[i][j][0] = (j > 0 ? dp[i][j-1][0] : 0) + 1;
                    dp[i][j][1] = (i > 0 ? dp[i-1][j][1] : 0) + 1;
                    dp[i][j][2] = (i > 0 && j > 0 ? dp[i-1][j-1][2] : 0) + 1;
                    dp[i][j][3] = (i > 0 && j+1 < n ? dp[i-1][j+1][3] : 0) + 1;
                    for (int d = 0; d < 4; d++) ans = Math.max(ans, dp[i][j][d]);
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun longestLine(mat: Array<IntArray>): Int {
        val m = mat.size
        val n = mat[0].size
        val dp = Array(m) { Array(n) { IntArray(4) } }
        var ans = 0
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (mat[i][j] == 1) {
                    dp[i][j][0] = if (j > 0) dp[i][j-1][0] + 1 else 1
                    dp[i][j][1] = if (i > 0) dp[i-1][j][1] + 1 else 1
                    dp[i][j][2] = if (i > 0 && j > 0) dp[i-1][j-1][2] + 1 else 1
                    dp[i][j][3] = if (i > 0 && j+1 < n) dp[i-1][j+1][3] + 1 else 1
                    for (d in 0..3) ans = maxOf(ans, dp[i][j][d])
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def longestLine(self, mat: list[list[int]]) -> int:
        m, n = len(mat), len(mat[0])
        dp = [[[0]*4 for _ in range(n)] for _ in range(m)]
        ans = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    dp[i][j][0] = (dp[i][j-1][0] if j > 0 else 0) + 1
                    dp[i][j][1] = (dp[i-1][j][1] if i > 0 else 0) + 1
                    dp[i][j][2] = (dp[i-1][j-1][2] if i > 0 and j > 0 else 0) + 1
                    dp[i][j][3] = (dp[i-1][j+1][3] if i > 0 and j+1 < n else 0) + 1
                    ans = max(ans, dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3])
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn longest_line(mat: Vec<Vec<i32>>) -> i32 {
        let m = mat.len();
        let n = mat[0].len();
        let mut dp = vec![vec![vec![0; 4]; n]; m];
        let mut ans = 0;
        for i in 0..m {
            for j in 0..n {
                if mat[i][j] == 1 {
                    dp[i][j][0] = if j > 0 { dp[i][j-1][0] } else { 0 } + 1;
                    dp[i][j][1] = if i > 0 { dp[i-1][j][1] } else { 0 } + 1;
                    dp[i][j][2] = if i > 0 && j > 0 { dp[i-1][j-1][2] } else { 0 } + 1;
                    dp[i][j][3] = if i > 0 && j+1 < n { dp[i-1][j+1][3] } else { 0 } + 1;
                    ans = ans.max(dp[i][j][0].max(dp[i][j][1]).max(dp[i][j][2]).max(dp[i][j][3]));
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    longestLine(mat: number[][]): number {
        const m = mat.length, n = mat[0].length;
        const dp = Array.from({length: m}, () => Array.from({length: n}, () => Array(4).fill(0)));
        let ans = 0;
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (mat[i][j] === 1) {
                    dp[i][j][0] = (j > 0 ? dp[i][j-1][0] : 0) + 1;
                    dp[i][j][1] = (i > 0 ? dp[i-1][j][1] : 0) + 1;
                    dp[i][j][2] = (i > 0 && j > 0 ? dp[i-1][j-1][2] : 0) + 1;
                    dp[i][j][3] = (i > 0 && j+1 < n ? dp[i-1][j+1][3] : 0) + 1;
                    ans = Math.max(ans, dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3]);
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(mn), where m and n are the dimensions of the matrix. We scan each cell once.
  • 🧺 Space complexity: O(mn), for the dp array.