Leetcode 0562 Longest Line of Consecutive One in Matrix

Problem statement

https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix/

Solution 1

dp table with size m x n x 4, where dp[i][j][0] is the maximum horizontal line with ones which ends in (i, j) point, dp[i][j][1] is vertical, and other two is for diagonals.

Complexity

Time and space complexity is O(4mn).

Code

class Solution:
    def longestLine(self, A):
        m, n = len(A), len(A[0])
        res = 0
        dp = [[[0]*4 for _ in range(n)] for _ in range(m)]
        for i,j in product(range(m), range(n)):
            if A[i][j] == 0: continue

            for k in range(4):
                dp[i][j][k] = 1
            if i - 1 >= 0:
                dp[i][j][0] += dp[i - 1][j][0]
            if j - 1 >= 0:
                dp[i][j][1] += dp[i][j - 1][1]
            if i - 1 >= 0 and j - 1 >= 0:
                dp[i][j][2] += dp[i - 1][j - 1][2]
            if i - 1 >= 0 and j + 1 < n:
                dp[i][j][3] += dp[i - 1][j + 1][3]
            res = max(res, max(dp[i][j]))
        return res

Solution 2

Or we can use lru_cache with the same complexity.

Complexity

Time and space complexity is O(4mn).

Code

class Solution:
    def longestLine(self, A):
        m, n = len(A), len(A[0])
        @lru_cache(None)
        def dp(x, y, dx, dy):
            if not 0 <= x < m or not 0 <= y < n: return 0
            if A[x][y] == 0: return 0
            return dp(x-dx, y-dy, dx, dy) + 1
        
        ans = 0
        for x, y in product(range(m), range(n)):
            for dx, dy in (1, 0), (0, 1), (1, 1), (1, -1):
                ans = max(ans, dp(x, y, dx, dy))
        return ans