hashtable solution
class Solution:
def longestLine(self, M: List[List[int]]) -> int:
"""
1. edge case: if M is empty
2. create 4 dictionary caches for 4 direction
3. loop through matrix M each time there is val == 1, keep incrementing cnt until encounter a '0', reset values corresponding to each cache's key
4. each time find a val == 1, compare them with global ans varible
tc O(R*C) sc O(max(R,C))
"""
if not M:
return 0
r = len(M)
c = len(M[0])
mx = 0
col = {}
row = {}
dia = {}
antD = {}
for i in range(r):
for j in range(c):
if M[i][j] == 1:
col[i] = col.get(i,0) +1
row[j] = row.get(j,0) + 1
dia[j-i] = dia.get(j-i,0) +1
antD[i+j] = antD.get(i+j,0) + 1
mx = max(mx, col[i], row[j], dia[j-i], antD[i+j])
else:
col[i],row[j], dia[j-i], antD[i+j] = 0,0,0,0
return mx
similar way but using matrix to cache
class Solution:
def longestLine(self, M: List[List[int]]) -> int:
"""
1. edge case: if M is empty
2. create 4 dictionary caches for 4 direction
3. loop through matrix M each time there is val == 1, keep incrementing cnt until encounter a '0', reset values corresponding to each cache's key
4. each time find a val == 1, compare them with global ans varible
tc O(R*C) sc O(max(R,C))
"""
if not M:
return 0
r = len(M)
c = len(M[0])
mx = 0
dp = [[[0 for _ in range(4)] for _ in range(c)] for _ in range(r)]
#print(len(dp[0][0]),len(dp[0]),len(dp))
for i in range(r):
for j in range(c):
if M[i][j] == 0:
continue
for k in range(4):
dp[i][j][k] = 1
#print(dp[i][j][0])
#(1)l -> r
if j> 0:
dp[i][j][0] += dp[i][j-1][0]
#(2) up -> down
if i>0 :
dp[i][j][1] += dp[i-1][j][1]
# (3) diag
if j>0 and i >0:
dp[i][j][2] += dp[i-1][j-1][2]
#(4) anti d
if j < c -1 and i > 0 :
dp[i][j][3] += dp[i-1][j+1][3]
mx = max(mx,dp[i][j][0],dp[i][j][1],dp[i][j][2],dp[i][j][3])
return mx