LC073 - Set Matrix Zeroes

Problem

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's. Must be in place.

Example

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]

Output: [[1,0,1],[0,0,0],[1,0,1]]

Solution

Time complexity of this solution is $O(m\cdot n)$ with extra space used for each zero in the matrix.

def setZeroes(self, matrix: List[List[int]]) -> None:
	zeroes = []
	for i in range(len(matrix)):
		for j in range(len(matrix[0])):
			if matrix[i][j] == 0:
				zeroes.append((i, j))

	for row, col in zeroes:
		matrix[row] = 0 * len(matrix[0])
		for i in range(len(matrix)):
			matrix[i][col] = 0