LeetCode 562: Longest Line of Consecutive One in Matrix
Problem Description
Explanation:
This problem asks us to find the longest line of consecutive 1s in a matrix. The matrix can have 4 directions where the consecutive 1s can be counted: horizontal, vertical, diagonal, and anti-diagonal.
We can solve this problem efficiently by iterating through the matrix and keeping track of the lengths of consecutive 1s in each direction. We can use dynamic programming to update the lengths based on the current cell's value and the neighboring cells.
Here are the steps for the algorithm:
- Initialize variables for the maximum length of consecutive 1s in each direction.
- Iterate through the matrix and update the lengths of consecutive 1s for each direction.
- Return the maximum length among all directions.
Time complexity: O(m*n) where m is the number of rows and n is the number of columns in the matrix. Space complexity: O(n) where n is the number of columns in the matrix.
:
Solutions
class Solution {
public int longestLine(int[][] mat) {
int m = mat.length;
if (m == 0) return 0;
int n = mat[0].length;
int[][][] dp = new int[m][n][4];
int maxLen = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) continue;
for (int k = 0; k < 4; k++) {
dp[i][j][k] = 1;
}
if (j > 0) dp[i][j][0] += dp[i][j-1][0]; // horizontal
if (i > 0) dp[i][j][1] += dp[i-1][j][1]; // vertical
if (i > 0 && j > 0) dp[i][j][2] += dp[i-1][j-1][2]; // diagonal
if (i > 0 && j < n-1) dp[i][j][3] += dp[i-1][j+1][3]; // anti-diagonal
maxLen = Math.max(maxLen, Math.max(dp[i][j][0], Math.max(dp[i][j][1], Math.max(dp[i][j][2], dp[i][j][3]))));
}
}
return maxLen;
}
}Related LeetCode Problems
Loading editor...