CODEWITHSUNDEEP
algorithmdynamic-programmingpython-3.7
Flupper
Flupper

Reputation: 321

Maximal square dp on same matrix

The question Maximal Square in https://leetcode.com/problems/maximal-square/description/ is easy to solve by DP. but instead of creating a new matrix, I modified on the original one but that approach failed with test case No. 64, please check my Following code and help me to figure out the missing point.

def maximalSquare(self, matrix: List[List[str]]) -> int:

    for x in range(1,len(matrix)):
        for y in range(1,len(matrix[x])):
            if matrix[x][y] == '1':
                matrix[x][y] = str(int(min( matrix[x-1][y], matrix[x][y-1], matrix[x-1][y-1]))+1)

    return int(max([max(x) for x in matrix])) ** 2 if matrix else 0

Upvotes: 0

Views: 89

Answers (1)

MIHIR UPADHYAY
MIHIR UPADHYAY

Reputation: 54

I guess you're not handling the corner cases. For me, this code runs fine with little changes. Also, this will run a little slow.

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix: return 0
        m, n, res = len(matrix), len(matrix[0]), 0
        for i in range(m):
            for j in range(n):
                if (i == 0 or j == 0) and (matrix[i][j] == '1'):
                    res = max(res, 1)
                elif int(matrix[i][j]) == 1:
                    matrix[i][j] = min(int(matrix[i-1][j]), int(matrix[i][j-1]), int(matrix[i-1][j-1])) + 1
                    res = max(res, matrix[i][j])
        return res ** 2

When iterating the first row or first column, the formula for dp(i, j) is checking for values out of bounds. By shifting the whole dp to the right and bottom by 1 and adding padding of 0's to the 1st row and 1st column, it makes the formula work without checking for boundaries.

Upvotes: 1

Related Questions