C++ Simple Solution, O(n*m) DP


  • 0

    39ms.
    Anyone can tell me, how to do it in 0ms?
    Submission Details shows that some submission can do it in 0ms.

    class Solution {
    public:
        int longestLine(vector<vector<int>>& M) {
            int m = M.size(), n = m ? M[0].size() : 0, res = 0;
            // anti-diagonal, vertical, digonal
            vector<vector<int>> dp(n, vector<int>(3, 0));
            for (int i = 0; i < m; i++) {
                int hor = 0, anti_diag_prev = 0;
                for (int j = 0; j < n; j++) {
                    int tmp = dp[j][0];
                    if (M[i][j] == 0) {
                        dp[j][0] = dp[j][1] = dp[j][2] = 0;
                        hor = 0;
                    } else {
                        hor++;
                        dp[j][0] = anti_diag_prev + 1;
                        dp[j][1] += 1;
                        dp[j][2] = (j + 1 < n ? dp[j + 1][2] : 0) + 1;
                    }
                    anti_diag_prev = tmp;
                    res = max(max(res, hor), max(dp[j][0], max(dp[j][1], dp[j][2])));
                }
            }
            return res;
        }
    };
    

  • 0

    That's not O(n) but O(mn).


  • 0

    @StefanPochmann Um, yes.... I have changed the title. Thank you.


Log in to reply
 

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