# Given a m x n matrix, if an element is 0, set its entire row and column to 0.
# Do it in place.
#
# click to show follow up.
#
# Follow up:
#
# Did you use extra space?
# A straight forward solution using O(mn) space is probably a bad idea.
# A simple improvement uses O(m + n) space, but still not the best solution.
# Could you devise a constant space solution?
class Solution():
def setZeroes(self, x):
row, col = [0]*len(x), [0]*len(x[0])
for i in range(len(x)):
for j in range(len(x[0])):
if x[i][j] == 0:
row[i], col[j] = 1, 1
for i in range(len(x)):
for j in range(len(x[0])):
if row[i] == 1 or col[j] == 1:
x[i][j] = 0
if __name__ == "__main__":
x = [[1, 0, 1, 1], [1, 1, 0, 1], [1, 1, 1, 0], [1, 1, 1, 1]]
Solution().setZeroes(x)
assert x == [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [1, 0, 0, 0]]