C++ O(mn) time O(m+n) space


  • 1
    T
    class Solution {
    public:
        int longestLine(vector<vector<int>>& M) {
            int h = M.size(), w = h ? M[0].size():0;
            if (!h) return 0;
            
            vector<int> row(h, 0), col(w, 0), diag(h+w+1, 0), adiag(h+w+1, 0);
            int maxlen = 0;
            for (int i = 0; i < h; ++i) {
                for (int j = 0; j < w; ++j) {
                    if (!M[i][j]) {
                        row[i] = col[j] = diag[w+i-j] = adiag[i+j] = 0;
                    } else {
                        ++row[i], ++col[j], ++diag[w+i-j], ++adiag[i+j];
                        maxlen = max(maxlen, max(row[i], max(col[j], max(diag[w+i-j], adiag[i+j]))));
                    }
                }
            }
            return maxlen;
        }
    };
    

Log in to reply
 

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