562 Longest Line of Consecutive One in Matrix

562. Longest Line of Consecutive One in Matrix​
1. Question
Given a 01 matrix M, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.
Example:
1
Input:
2
[[0,1,1,0],
3
 [0,1,1,0],
4
 [0,0,0,1]]
5
​
6
Output: 3
Copied!
Hint: The number of elements in the given matrix will not exceed 10,000.
2. Implementation
(1) DP
1
public class Solution {
2
    public int longestLine(int[][] M) {
3
        if (M == null || M.length == 0) {
4
            return 0;
5
        }
6
​
7
        int m = M.length, n = M[0].length;
8
        int res = 0;
9
​
10
        // dp[i][j][0] means the longest consecutive 1 horizontally at (i, j)
11
        // dp[i][j][1] means the longest consecutive 1 vertically at (i, j)
12
        // dp[i][j][2] means the longest consecutive 1 diagnolly at (i, j)
13
        // dp[i][j][3] means the longest consecutive 1 anti-diagnolly (i, j)
14
        int[][][] dp = new int[m][n][4];
15
​
16
        for (int i = 0; i < m; i++) {
17
            for (int j = 0; j < n; j++) {
18
                if (M[i][j] == 1) {
19
                    // Horizontal
20
                    dp[i][j][0] = j > 0 ? dp[i][j - 1][0] + 1 : 1;
21
                    // Vertical
22
                    dp[i][j][1] = i > 0 ? dp[i - 1][j][1] + 1 : 1;
23
                    // Diagnol
24
                    dp[i][j][2] = (i > 0 && j > 0) ? dp[i - 1][j - 1][2] + 1 : 1;
25
                    // Anti-Diagnol
26
                    dp[i][j][3] = (i > 0 && j < n - 1) ? dp[i - 1][j + 1][3] + 1 : 1;
27
                    res = Math.max(res, Math.max(dp[i][j][0], dp[i][j][1]));
28
                    res = Math.max(res, Math.max(dp[i][j][2], dp[i][j][3]));
29
                }
30
            }
31
        }
32
        return res;
33
    }
34
}
Copied!
3. Time & Space Complexity
DP: 时间复杂度O(mn), 空间复杂度O(mn)

552 Student Attendance Record II

568 Maximum Vacation Days

Last modified 2yr ago

Copy link

Contents

562. Longest Line of Consecutive One in Matrix

1. Question

2. Implementation

3. Time & Space Complexity

562. Longest Line of Consecutive One in Matrix​

1. Question

2. Implementation

3. Time & Space Complexity

562. Longest Line of Consecutive One in Matrix