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


  • 0
    T
    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;
        }
    };
    

Log in to reply
 

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