clueless coding // TODO: be smarter

LeetCode Longest Line of Consecutive One in Matrix: CPP Solution



TL;DR Code Solution


    // 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;
    }