A question on dynamic programming leetcode problem 221

Question

I'm a beginner in Python. The following is my code for leetcode 221 (Maximal Square), it can only pass more than 30 test samples. It fails at the matrix: M=[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]].

def maximalSquare(matrix):
    colleng=len(matrix)
    rowleng=len(matrix[0])
    maxsqlst=[]
    dp=[[0]*rowleng]*colleng
    for i in range(colleng):
        for j in range(rowleng):
            if matrix[i][j]=='1':
                if i==0 or j==0:
                    print('A',i,j,dp)
                    dp[i][j]=1
                    print('B',i,j,dp)
                else:
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
            print(i,j,dp)
        maxsqlst.append(max(dp[i]))

    return max(maxsqlst)**2

By inserting some print() command, I find that it goes wrong when i=j=0,

A 0 0 [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
B 0 0 [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0]].

Why does it make the first colume to be 1 instead of just dp[0][0]?

Thanks for your comment! When i=j=0, I hope it only set dp[0][0] to be 1, but it actually set the first colume of dp to 1. Why does that happen?@drum — RH W, Oct 22 '21 at 14:56

Joshua Voskamp · Answer 1 · 2021-10-22T15:00:48.507

TL;DR: Change your definition of dp from

dp = [[0]*rowleng]*colleng

to

dp = [[0 for i in range(rowleng)] for j in range(colleng)]

Why? In the first, you're creating a 2D list of references to the same list; in the second, you're creating a 2D list of references to unique lists.

(Technically, you could rewrite the 2nd lind as dp = [[0]*rowleng for j in range(colleng)] and get the same result.)

All that to say, when you declare dp to be a list of references to the same list, then when you change dp[0][0], it "also changes" dp[i][0] for all 0 < i < len(dp) -- because it's all the same list being referred to.

See e.g. List of lists changes reflected across sublists unexpectedly for more info.

score 0 · Answer 2 · answered Oct 22 '21 at 14:57

In your function, you call this line:

dp[i][j]=1

This sets the item of i and j to 1, and if you notice the section where its called:

if matrix[i][j]=='1':
    if i==0 or j==0:

You will notice that both of those conditions are true in the cases you get 1, as this value is overriding whatever other values you've had, at least from what I see.

Remember that you are comparing with an or and not an and, so if either i or j were zero, not both necessarily, you will end up overriding the value, especially in locations where your matrix is equal to 1 (Here, your first column is all ones).

A question on dynamic programming leetcode problem 221

2 Answers2