C# simple solution - O(mn) time, O(1) extra space


  • 0
    S
    public class Solution 
    {
        int Longest(int[,] M, IEnumerable<Tuple<int, int>> start, int dr, int dc)
        {
            int nRows = M.GetLength(0);
            int nCols = M.GetLength(1);
            
            int res = 0;
            foreach(var s in start)
            {
                int r = s.Item1, c = s.Item2;
                int cur = 0;
                while(r >= 0 && c >= 0 && r < nRows && c < nCols)
                {
                    if(M[r, c] == 1)
                        cur++;
                    else
                    {
                        res = Math.Max(cur, res);
                        cur = 0;
                    }
                    r += dr;
                    c += dc;
                }
                
                res = Math.Max(cur, res);
            }
            
            return res;
        }
        
        public int LongestLine(int[,] M) 
        {
            int res = 0;
            int nRows = M.GetLength(0);
            int nCols = M.GetLength(1);
            
            res = Math.Max(res, Longest(M, Enumerable.Range(0, nRows).Select(r => Tuple.Create(r, 0)), 0, 1));
            res = Math.Max(res, Longest(M, Enumerable.Range(0, nCols).Select(c => Tuple.Create(0, c)), 1, 0));
            res = Math.Max(res, Longest(M, Enumerable.Range(0, nRows).Select(r => Tuple.Create(r, 0)), 1, 1));
            res = Math.Max(res, Longest(M, Enumerable.Range(0, nCols).Select(c => Tuple.Create(0, c)), 1, 1));
            res = Math.Max(res, Longest(M, Enumerable.Range(0, nRows).Select(r => Tuple.Create(r, 0)), -1, 1));
            res = Math.Max(res, Longest(M, Enumerable.Range(0, nCols).Select(c => Tuple.Create(nRows - 1, c)), -1, 1));
            
            return res;
        }
    }
    

Log in to reply
 

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