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])