[C++] Solution - No Cache


  • 4
    class Solution {
    public:
        int longestLine(vector<vector<int>>& M) {
            if (M.empty() || M[0].empty()) {
                return 0;
            }
            int m = M.size(), n = M[0].size();
            int maxl = 0, hori = 0, vert = 0, inc = 0, desc = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0, hori = 0; j < n; j++) {
                    hori = M[i][j] ? hori + 1 : 0;
                    maxl = max(maxl, hori);
                }
            }
            for (int j = 0; j < n; j++) {
                for (int i = 0, vert = 0; i < m; i++) {
                    vert = M[i][j] ? vert + 1 : 0;
                    maxl = max(maxl, vert);
                }
            }
            for (int k = 0; k < m + n; k++) {
                // increasing start from left cells then bottom cells
                for (int i = min(k, m - 1), j = max(0, k - m), inc = 0; i >= 0 && j < n; i--, j++) {
                    inc = M[i][j] ? inc + 1 : 0;
                    maxl = max(maxl, inc);
                }
                // decreasing start from left cells then top cells;
                for (int i = max(m - 1 - k, 0), j = max(0, k - m), desc = 0; i < m && j < n; i++, j++) {
                    desc = M[i][j] ? desc + 1 : 0;
                    maxl = max(maxl, desc);
                }
            }
            return maxl;
        }
    };
    

  • 0
    Z

    Good code! Same performance as DP with O(1) space. DP is not necessary.


Log in to reply
 

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