Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/562.html
562. Longest Line of Consecutive One in Matrix
Level
Medium
Description
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:
Input:
[[0,1,1,0],
[0,1,1,0],
[0,0,0,1]]
Output: 3
Hint: The number of elements in the given matrix will not exceed 10,000.
Solution
Create an array lines of size M.length * M[0].length * 4, where lines[i][j][k] represents the longest line of consecutive ones in the matrix that ends at position (i, j) in direction k. The 4 directions are horizontal, vertical, diagonal and anti-diagonal.
Loop over M from the first row to the last row, and from the first column to the last column for each row. If an element is 1, then update the corresponding elements in lines, considering the previous positions where the elements are 1. Update the maximum length after each update. Finally, return the maximum length.
-
class Solution { public int longestLine(int[][] M) { if (M == null || M.length == 0 || M[0].length == 0) return 0; int maxLength = 0; int rows = M.length, columns = M[0].length; int[][][] lines = new int[rows][columns][4]; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { if (M[i][j] == 1) { for (int k = 0; k < 4; k++) lines[i][j][k] = 1; if (j > 0 && M[i][j - 1] == 1) lines[i][j][0] = lines[i][j - 1][0] + 1; if (i > 0 && M[i - 1][j] == 1) lines[i][j][1] = lines[i - 1][j][1] + 1; if (i > 0 && j > 0 && M[i - 1][j - 1] == 1) lines[i][j][2] = lines[i - 1][j - 1][2] + 1; if (i > 0 && j < columns - 1 && M[i - 1][j + 1] == 1) lines[i][j][3] = lines[i - 1][j + 1][3] + 1; for (int k = 0; k < 4; k++) maxLength = Math.max(maxLength, lines[i][j][k]); } } } return maxLength; } } -
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): v = mat[i - 1][j - 1] if v: 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 ############ class Solution(object): def longestLine(self, M): """ :type M: List[List[int]] :rtype: int """ if not M: return 0 hor = [[0] * (len(M[0]) + 2) for _ in range(len(M) + 1)] ver = [[0] * (len(M[0]) + 2) for _ in range(len(M) + 1)] diag = [[0] * (len(M[0]) + 2) for _ in range(len(M) + 1)] anti = [[0] * (len(M[0]) + 2) for _ in range(len(M) + 1)] ans = 0 for i in range(len(M)): for j in range(len(M[0])): if M[i][j] == 1: hor[i + 1][j + 1] = hor[i + 1][j] + 1 ver[i + 1][j + 1] = ver[i][j + 1] + 1 diag[i + 1][j + 1] = diag[i][j] + 1 anti[i + 1][j + 1] = anti[i][j + 2] + 1 ans = max(ans, hor[i + 1][j + 1], ver[i + 1][j + 1], diag[i + 1][j + 1], anti[i + 1][j + 1]) return ans -
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; } }; -
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 }