Skip to content

562. Longest Line of Consecutive One in Matrix πŸ”’

Description

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.

 

Example 1:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

Example 2:

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 <= 104
  • 1 <= m * n <= 104
  • mat[i][j] is either 0 or 1.

Solutions

Solution 1: Dynamic Programming

Thinking

The longest run of ones may go horizontally, vertically, or on either diagonal. Extending from every start is \(O(mn \cdot (m+n))\).

Four tables store the run ending at \((i,j)\) in each direction, taking the cell above, left, upper-left, or upper-right plus one. Zeros stay zero. A one-cell border avoids bounds checks. Track the global maximum.

We define \(f[i][j][k]\) to represent the length of the longest consecutive \(1\)s ending at \((i, j)\) in direction \(k\). The value range of \(k\) is \(0, 1, 2, 3\), representing horizontal, vertical, diagonal, and anti-diagonal directions, respectively.

We can also use four 2D arrays to represent the length of the longest consecutive \(1\)s in the four directions.

We traverse the matrix, and when we encounter \(1\), we update the value of \(f[i][j][k]\). For each position \((i, j)\), we only need to update the values in its four directions. Then we update the answer.

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\), where \(m\) and \(n\) are the number of rows and columns in the matrix, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def longestLine(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        a = [[0] * (n + 2) for _ in range(m + 2)]
        b = [[0] * (n + 2) for _ in range(m + 2)]
        c = [[0] * (n + 2) for _ in range(m + 2)]
        d = [[0] * (n + 2) for _ in range(m + 2)]
        ans = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if mat[i - 1][j - 1]:
                    a[i][j] = a[i - 1][j] + 1
                    b[i][j] = b[i][j - 1] + 1
                    c[i][j] = c[i - 1][j - 1] + 1
                    d[i][j] = d[i - 1][j + 1] + 1
                    ans = max(ans, a[i][j], b[i][j], c[i][j], d[i][j])
        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
class Solution {
    public int longestLine(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] a = new int[m + 2][n + 2];
        int[][] b = new int[m + 2][n + 2];
        int[][] c = new int[m + 2][n + 2];
        int[][] d = new int[m + 2][n + 2];
        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (mat[i - 1][j - 1] == 1) {
                    a[i][j] = a[i - 1][j] + 1;
                    b[i][j] = b[i][j - 1] + 1;
                    c[i][j] = c[i - 1][j - 1] + 1;
                    d[i][j] = d[i - 1][j + 1] + 1;
                    ans = max(ans, a[i][j], b[i][j], c[i][j], d[i][j]);
                }
            }
        }
        return ans;
    }

    private int max(int... arr) {
        int ans = 0;
        for (int v : arr) {
            ans = Math.max(ans, v);
        }
        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
class Solution {
public:
    int longestLine(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> a(m + 2, vector<int>(n + 2));
        vector<vector<int>> b(m + 2, vector<int>(n + 2));
        vector<vector<int>> c(m + 2, vector<int>(n + 2));
        vector<vector<int>> d(m + 2, vector<int>(n + 2));
        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (mat[i - 1][j - 1]) {
                    a[i][j] = a[i - 1][j] + 1;
                    b[i][j] = b[i][j - 1] + 1;
                    c[i][j] = c[i - 1][j - 1] + 1;
                    d[i][j] = d[i - 1][j + 1] + 1;
                    ans = max(ans, max(a[i][j], max(b[i][j], max(c[i][j], d[i][j]))));
                }
            }
        }
        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
func longestLine(mat [][]int) (ans int) {
    m, n := len(mat), len(mat[0])
    f := make([][][4]int, m+2)
    for i := range f {
        f[i] = make([][4]int, n+2)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if mat[i-1][j-1] == 1 {
                f[i][j][0] = f[i-1][j][0] + 1
                f[i][j][1] = f[i][j-1][1] + 1
                f[i][j][2] = f[i-1][j-1][2] + 1
                f[i][j][3] = f[i-1][j+1][3] + 1
                for _, v := range f[i][j] {
                    if ans < v {
                        ans = v
                    }
                }
            }
        }
    }
    return
}

Comments