0

I am programming in Python3 and am attempting to make a function which finds all of the zeros in a matrix and sets that element's entire row and column to zero.

It seems to me that the breadth first search I am using below should work, but I am encountering a strange problem: every time I attempt to change an element in used to 1 with the line: used[t[0]][t[1]] = 1 (indicating that position in the matrix has already been set), it also changes every element in that column to 1.

If you run this code using the matrix [[1, 1], [1, 0]] the first two print statements yield:

[[0, 0], [0, 0]]

[[0, 1], [0, 1]]

I don't understand how this is possible. There is only one line of code in between the two print statements and it only changes one element, yet when I print the array, two elements are modified. What exactly am I missing?

def setZeroes(self, matrix: List[List[int]]) -> None:
        used = [[0] * len(matrix[0])] * len(matrix)
            
        for i in range(0, len(matrix)):
            for j in range(0, len(matrix[i])):
                if matrix[i][j] == 0 and used[i][j] == 0:
                    queue = [[i, j]]
                    while(queue):
                        t = queue.pop(0)
                        print(used)
                        used[t[0]][t[1]] = 1
                        print(used)
                        if matrix[t[0]][t[1]] != 0:
                            matrix[t[0]][t[1]] = 0 
                            
                        else:
                            for k in range(0, len(matrix)):
                                if used[k][t[1]] == 0:
                                    queue.append([k, t[1]])
                                
                            for k in range(0, len(matrix[i])):
                                if used[t[0]][k] == 0:
                                    queue.append([t[0], k])
  • You're creating a matrix (```used```) with multiple references to the same list. See [this thread](https://stackoverflow.com/questions/240178/list-of-lists-changes-reflected-across-sublists-unexpectedly) for more details. – sj95126 Aug 22 '21 at 14:58

0 Answers0