C++ O(mn) time O(1) concise solution


  • 0
    G
    class Solution {
    public:
        // Only search the starting points. O(mn) time, O(1) space
        int longestLine(vector<vector<int>>& M) {
            int m = M.size();
            if (m == 0) return 0;
            int n = M[0].size();
            int len = 0;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (M[i][j] == 1) {
                        if (j == 0 || M[i][j-1] == 0) len = max(len, count(M,i,j,0,1));  // horizontal
                        if (i == 0 || M[i-1][j] == 0) len = max(len, count(M,i,j,1,0));  // vertical
                        if (i == 0 || j == 0 || M[i-1][j-1] == 0) len = max(len, count(M,i,j,1,1)); //  anti diag
                        if (i == 0 || j == 0 || M[i-1][j+1] == 0) len = max(len, count(M,i,j,1,-1));  // diag
                    }
                }
            }
            return len;
        }
    private:
        int count(vector<vector<int>>& M, int i, int j, int deltai, int deltaj) {
            int len = 0;
            while (i < M.size() && j < M[0].size() && M[i][j] == 1) {
                i += deltai;
                j += deltaj;
                ++len;
            }
            return len;
        }
    };
    

Log in to reply
 

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