# https://leetcode.com/problems/set-matrix-zeroes/
# 73. Set Matrix Zeroes
# # Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
# # Example 1:
# # Input:
# [
#   [1,1,1],
#   [1,0,1],
#   [1,1,1]
# ]
# Output:
# [
#   [1,0,1],
#   [0,0,0],
#   [1,0,1]
# ]
# Example 2:
# Input:
# [
#   [0,1,2,0],
#   [3,4,5,2],
#   [1,3,1,5]
# ]
# Output:
# [
#   [0,0,0,0],
#   [0,4,5,0],
#   [0,3,1,0]
# ]
# Follow up:
#
#     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?

def setZeroes(matrix):
    r, c = [], []
    for x in matrix:
        for y in matrix[x]:
            if matrix[x][y] == 0:
                r.append(x)
                c.append(y)
    for x in r:
        for y in matrix[x]:
            matrix[x][y] = 0
    for y in c:
        for x in matrix:
            matrix[x][y] = 0
    return matrix
