Recursive
To find the largest square, We'd go to the first "1" and ask it, "Hey, what's the largest square of 1s that begins with you?". To calculate that it needs to know the largest squares its adjacent cells can begin. So, it'll ask the same question to its adjacent cells which will, in turn, will ask their adjacent cells and so on... The cell that began the question will deduce that the largest square that begins with it is 1 + the minimum of all the values its adjacent cells returned.
You'd then ask the same question to every "1" you find in the grid and keep track of the global maximum. In doing so, you'll notice that the recursion causes many cells to be asked the same question again and again (overlapping sub-problems)- so you'd use memoization.
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
r,c = len(matrix),len(matrix[0])
mx = 0
@lru_cache(None)
def rec(i,j):
if i>=r or j>=c:
return 0
if matrix[i][j]=="1":
a1 = rec(i+1,j)
a2 = rec(i,j+1)
a3 = rec(i+1,j+1)
ans = 1+min(a1, a2, a3)
return ans
else:
return 0
for i in range(r):
for j in range(c):
if matrix[i][j]=="1":
mx = max(mx,rec(i,j))
return mx*mx
Iterative
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
r,c = len(matrix),len(matrix[0])
mx = 0
dp = [[0 for j in range(c+1)] for i in range(r+1)]
mx = 0
for i in range(1,r+1):
for j in range(1,c+1):
if matrix[i-1][j-1]=="1":
dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
mx = max(mx,dp[i][j])
else:
dp[i][j]=0
return mx*mx
#leetcode #algorithms #dynamicprogramming