Java O(nm) Time DP Solution

• ``````public int longestLine(int[][] M) {
int n = M.length, max = 0;
if (n == 0) return max;
int m = M[0].length;
int[][][] dp = new int[n][m][4];
for (int i=0;i<n;i++)
for (int j=0;j<m;j++) {
if (M[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 line
if (j > 0 && i > 0) dp[i][j][1] += dp[i-1][j-1][1]; // anti-diagonal line
if (i > 0) dp[i][j][2] += dp[i-1][j][2]; // vertical line
if (j < m-1 && i > 0) dp[i][j][3] += dp[i-1][j+1][3]; // diagonal line
max = Math.max(max, Math.max(dp[i][j][0], dp[i][j][1]));
max = Math.max(max, Math.max(dp[i][j][2], dp[i][j][3]));
}
return max;
}
``````

Note that each cell of the DP table only depends on the current row or previous row so you can easily optimize the above algorithm to use only O(m) space.

• Clean code and easy to understand. Thanks!

• Did you interchange diagonal and anti-diagonal comments?
And shouldn't you be doing max = max of (dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3], max)?

• @gova2009 thats what @compton_scatter is doing in the last two lines of the second for loop to get the max

• My bad, I didn't observe the nested Math.max.
But the comment should be reversed, isn't it?

• @gova2009 the comments are valid. diagonal is left to right and downwards and anti-diagonal is left to right and upwards

• @compton_scatter clear and simple, like it.

• @gova2009 it will have the same result, I believe.

• I also solved it using similar Idea.

``````    int [] rdir = new int [] { 0, 1, 1,  1 };
int [] cdir = new int [] { 1, 1, 0, -1 };

public int longestLine(int[][] M) {
if (M.length == 0) return 0;
int max = 0;

int [][][] dp = new int [M.length][M [0].length][4];

for (int row = 0; row < M.length; row ++)
for (int col = 0; col < M [0].length; col ++)
if (M [row][col] == 1)
for (int idx = 0; idx < 4; idx ++) max = Math.max (max, dfs (M, dp, row, col, idx));

return max;
}

private int dfs (int [][] M, int [][][] dp, int row, int col, int idx) {
if (row < 0 || row >= M.length || col < 0 || col >= M [0].length || M [row][col] != 1) return 0;
if (dp [row][col][idx] != 0) return dp [row][col][idx];
int count = 1;
count += dfs (M, dp, row + rdir [idx], col + cdir [idx], idx);
return dp [row][col][idx] = count;
}
``````

• @kmv

I do think it interchanges diagonal and anti-diagonal comments.

``````if (j > 0 && i > 0) dp[i][j][1] += dp[i-1][j-1][1]; // anti-diagonal line (wrong. should diagonal line)
if (i > 0) dp[i][j][2] += dp[i-1][j][2]; // vertical line
if (j < m-1 && i > 0) dp[i][j][3] += dp[i-1][j+1][3]; // diagonal line (wrong. should anti-diagonal line)
``````

• can anybody explain why we are initializing to 1

for (int k=0;k<4;k++) dp[i][j][k] = 1;

• Space complexity optimization: O(n)

``````class Solution {
public int longestLine(int[][] M) {
int result = 0;
if (M.length == 0 || M[0].length == 0) {
return 0;
}
int[][][] record = new int[2][M[0].length + 2][4];
for (int i = 1; i <= M.length; i++) {
for (int j = 1; j <= M[0].length; j++) {
if (M[i - 1][j - 1] == 1) {
record[i%2][j][0] = record[(i - 1) % 2][j][0] + 1;
record[i%2][j][1] = record[i % 2][j - 1][1] + 1;
record[i%2][j][2] = record[(i - 1) % 2][j - 1][2] + 1;
record[i%2][j][3] = record[(i - 1) % 2][j + 1][3] + 1;
for (int k = 0; k < 4; k++) {
result = Math.max(result, record[i % 2][j][k]);
}
} else {
for (int k = 0; k < 4; k++) {
record[i%2][j][k] = 0;
}
}
}
}
return result;
}
}
``````

• Great solution! Slightly modified to use direction vector and move dp[i][j][k] = 1 to the same loop that we're try different direction:

``````public int longestLine(int[][] M) {
int m = M.length, max = 0;
if (m == 0) return max;
int n = M[0].length;
int[][][] dp = new int[m][n][4];
int[][] dir = new int[][]{{-1, 0}, {0, -1}, {-1, -1}, {-1, 1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (M[i][j] == 0) continue;
for (int k = 0; k < 4; k++) {
dp[i][j][k] = 1;
int prevI = i + dir[k][0];
int prevJ = j + dir[k][1];
if (isValid(M, prevI, prevJ)) dp[i][j][k] += dp[prevI][prevJ][k];
max = Math.max(max, dp[i][j][k]);
}
}
}
return max;
}

private boolean isValid(int[][] M, int i, int j) {
return i < M.length && i >= 0 && j < M[0].length && j >= 0;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.