# [Java/C++] Clean Code - No Cache

• Java

``````class Solution {
public int longestLine(int[][] M) {
if (M.length == 0 || M[0].length == 0) return 0;
int m = M.length, n = M[0].length;
int max = 0, hori = 0, vert = 0, inc = 0, desc = 0;
for (int i = 0; i < m; i++, hori = 0) {
for (int j = 0; j < n; j++) {
hori = M[i][j] > 0 ? hori + 1 : 0;
max = Math.max(max, hori);
}
}
for (int j = 0; j < n; j++, vert = 0) {
for (int i = 0; i < m; i++) {
vert = M[i][j] > 0 ? vert + 1 : 0;
max = Math.max(max, vert);
}
}
for (int k = 0; k < m + n; k++, inc = 0, desc = 0) {
// increasing start from left cells then bottom cells
for (int i = Math.min(k, m - 1), j = Math.max(0, k - m); i >= 0 && j < n; i--, j++) {
inc = M[i][j] > 0 ? inc + 1 : 0;
max = Math.max(max, inc);
}
// decreasing start from left cells then top cells;
for (int i = Math.max(m - 1 - k, 0), j = Math.max(0, k - m); i < m && j < n; i++, j++) {
desc = M[i][j] > 0 ? desc + 1 : 0;
max = Math.max(max, desc);
}
}
return max;
}
}
``````

c++

``````class Solution {
public:
int longestLine(vector<vector<int>>& M) {
if (M.empty() || M[0].empty()) return 0;
int m = M.size(), n = M[0].size();
int maxl = 0, hori = 0, vert = 0, inc = 0, desc = 0;
for (int i = 0; i < m; i++)
for (int j = 0, hori = 0; j < n; j++, maxl = max(maxl, hori))
hori = M[i][j] ? hori + 1 : 0;

for (int j = 0; j < n; j++)
for (int i = 0, vert = 0; i < m; i++, maxl = max(maxl, vert))
vert = M[i][j] ? vert + 1 : 0;

for (int k = 0; k < m + n; k++) {
for (int i = min(k, m - 1), j = max(0, k - m), inc = 0; i >= 0 && j < n; i--, j++, maxl = max(maxl, inc))
inc = M[i][j] ? inc + 1 : 0;
for (int i = max(m - 1 - k, 0), j = max(0, k - m), desc = 0; i < m && j < n; i++, j++, maxl = max(maxl, desc))
desc = M[i][j] ? desc + 1 : 0;
}
return maxl;
}
};
``````

• Good code! Same performance as DP with O(1) space. DP is not necessary.

• Beat 95% of the other solutions.
Similar idea, but only iterate the grid once. The basic idea is simple, take horizontal for example: when we see 1, if the left number is 0 then count the consecutive ones from this position on, and the update max. The second 1 from 1-1 sequence will be skipped. so the time complexity would be O(mn).

``````public int longestLine(int[][] M) {
if (M.length == 0 || M[0].length == 0) return 0;
int r = M.length, c = M[0].length, max = 0;
for (int i = 0; i < r; i ++) {
for (int j = 0; j < c; j++) {
int curRow = 0, curCol = 0, diag = 0, anti = 0;
if (M[i][j] == 1) {
if (j == 0 || M[i][j-1] == 0) {
int col = j;
while (col < c && M[i][col] == 1) {
curRow++;
col++;
}
max = Math.max(max, curRow);
}
if (i == 0 || M[i-1][j] == 0) {
int row = i;
while (row<r && M[row][j] == 1) {
curCol++;
row++;
}
max = Math.max(max, curCol);
}

if (i == 0 || j == 0 || M[i-1][j-1] == 0) {
int row = i, col = j;
while (row <r && col < c && M[row][col] == 1) {
diag++;
row++; col++;
}
max = Math.max(max, diag);
}

if (i == 0 || j == c-1 || M[i-1][j+1] == 0) {
int row = i, col = j;
while (row <r && col >=0 && M[row][col] == 1) {
anti++;
row++; col--;
}
max = Math.max(max, anti);
}
}
}
}
return max;
}
``````

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