# C++, one Scan, time Complexity O(mn), space Complexity O(1)

• ``````class Solution {
public:
int longestLine(vector<vector<int>>& M)
{
int result = 0;
for (int i = 0; i < M.size(); i++)
{
for (int j = 0; j < M[i].size(); j++)
{
if (M[i][j] == 1)
{
if (i - 1 < 0 || M[i - 1][j] != 1)
{
int r = 1;
int x = i + 1;
while (x < M.size() && M[x][j] == 1)
{
r++;
x++;
}

result = max(result, r);
}
if (j - 1<0 || M[i][j - 1] != 1)
{
int r = 1;
int y = j + 1;
while (y < M[i].size() && M[i][y] == 1)
{
y++;
r++;
}

result = max(result, r);
}
if (i - 1 < 0 || j - 1 < 0 || M[i - 1][j - 1] != 1)
{
int r = 1;
int x = i + 1;
int y = j + 1;
while (x < M.size() && y < M[x].size() && M[x][y] == 1)
{
r++;
x++;
y++;
}

result = max(result, r);
}
if (i - 1 < 0 || j + 1 >= M[i-1].size() || M[i - 1][j + 1] != 1)
{
int r = 1;
int x = i + 1;
int y = j - 1;
while (x < M.size() && y >= 0 && M[x][y] == 1)
{
r++;
x++;
y--;
}

result = max(result, r);
}
}
}
}
return result;
}
};
``````

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