DP Solution w/ Python & C++


  • 0
    Z

    python solution, O(NM) time, O(NM) space

    class Solution(object):
        def longestLine(self, M):
            """
            :type M: List[List[int]]
            :rtype: int
            """
            n, m, ll = len(M), len(M[0]) if M else 0, 0
            dp = [[[0, 0, 0 ,0] for j in xrange(m + 2)] for i in xrange(n + 1)]
            for i in xrange(n):
                for j in xrange(m):
                    if M[i][j] == 1:
                        dp[i+1][j+1][0] = dp[i+1][j][0] + 1
                        dp[i+1][j+1][1] = dp[i][j][1] + 1
                        dp[i+1][j+1][2] = dp[i][j+1][2] + 1
                        dp[i+1][j+1][3] = dp[i][j+2][3] + 1
                        ll = max(ll, max(dp[i+1][j+1]))
            return ll
    

    notice that we only need previous dp row, we can reduce it to O(N) space

    class Solution(object):
        def longestLine(self, M):
            """
            :type M: List[List[int]]
            :rtype: int
            """
            n, m, ll = len(M), len(M[0]) if M else 0, 0
            dp = [[[0, 0, 0 ,0] for j in xrange(m + 2)] for i in xrange(2)]
            for i in xrange(n):
                for j in xrange(m):
                    if M[i][j] == 1:
                        dp[1][j+1][0] = dp[1][j][0] + 1
                        dp[1][j+1][1] = dp[0][j][1] + 1
                        dp[1][j+1][2] = dp[0][j+1][2] + 1
                        dp[1][j+1][3] = dp[0][j+2][3] + 1
                        ll = max(ll, max(dp[1][j+1]))
                dp[0], dp[1] = dp[1], dp[0]
                for j in xrange(1, m + 1):
                    dp[1][j][:] = [0] * 4
            return ll
    

    c++ solution

    class Solution {
    public:
        int longestLine(vector<vector<int>>& M) {
            int n = M.size(), m = n == 0 ? 0 : M[0].size(), ll = 0;
            vector<int> pre(4 * m + 8), cur(4 * m + 8);
            for ( int i = 0; i < n; ++i ) {
                for ( int j = 0; j < m; ++j ) {
                    if ( M[i][j] ) {
                        cur[4 * j + 4] = cur[4 * j] + 1; // left
                        cur[4 * j + 5] = pre[4 * j + 1] + 1; // left top
                        cur[4 * j + 6] = pre[4 * j + 6] + 1; // top
                        cur[4 * j + 7] = pre[4 * j + 11] + 1; // right top
                    }
                }
                ll = max(ll, *max_element(cur.begin(), cur.end()));
                pre = cur;
                fill(cur.begin(), cur.end(), 0);
            }
            return ll;
        }
    };
    

Log in to reply
 

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