# [C++] Solution - No Cache

• ``````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++) {
hori = M[i][j] ? hori + 1 : 0;
maxl = max(maxl, hori);
}
}
for (int j = 0; j < n; j++) {
for (int i = 0, vert = 0; i < m; i++) {
vert = M[i][j] ? vert + 1 : 0;
maxl = max(maxl, vert);
}
}
for (int k = 0; k < m + n; k++) {
// increasing start from left cells then bottom cells
for (int i = min(k, m - 1), j = max(0, k - m), inc = 0; i >= 0 && j < n; i--, j++) {
inc = M[i][j] ? inc + 1 : 0;
maxl = max(maxl, inc);
}
// decreasing start from left cells then top cells;
for (int i = max(m - 1 - k, 0), j = max(0, k - m), desc = 0; i < m && j < n; i++, j++) {
desc = M[i][j] ? desc + 1 : 0;
maxl = max(maxl, desc);
}
}
return maxl;
}
};
``````

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

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