CODEWITHSUNDEEP
pythonalgorithmmatrixdata-structuresdynamic-programming
Rafael
Rafael

Reputation: 671

Error in finding the maximum square of 1s inside a matrix

I am trying to solve a problem wherein I have to find the maximum square of 1s inside a matrix, containing only zeroes and ones.

Full statement is here: https://leetcode.com/problems/maximal-square/description/

My solution is:

 def maximalSquare(matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """

        if len(matrix)==0:
            return 0

        maxlen = 0

        dp = [[0 for x in range(len(matrix[0])+1)] for x in range(len(matrix)+1)]

        for i in range(1, len(matrix)+1):
            for j in range(1, len(matrix[0])+1):
                if matrix[i-1][j-1]==1:
                    dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
                    maxlen = max(dp[i][j], maxlen)

        return maxlen

Sample Run:

Your input
[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Your answer
0
Expected answer
4

Now, my logic is simple: if three ones are there arranged in an L shape, the fourth one indicates that a square is present.

But the answer is off by a lot, what is the error I can't really find.

Upvotes: 0

Views: 94

Answers (1)

Arndt Jonasson
Arndt Jonasson

Reputation: 854

Since the matrix contains strings, the comparison should be

matrix[i-1][j-1]=="1"

rather than

matrix[i-1][j-1]==1

Upvotes: 2

Related Questions