Set Matrix Zeros

Question

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Example Given a matrix

[
  [1,2],
  [0,3]
],

return [ [0,2], [0,0] ]

Challenge 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?

Thoughts

O(m+n) space

用 dictionary记录下要set成0的行和列

in place

set matrix zeros 用第一行和第一列做记录 分为四步：

Step 1: First row contains zero = true; First column contains zero = false;

Step 2: use first row and column to mark zero row and column. set-matrix-zero-2

Step 3: set each elements by using marks in first row and column. set-matrix-zero-3

Step 4: Set first column and row by using marks in step 1.

Solution

class Solution:
    """
    @param matrix: A list of lists of integers
    @return: Nothing
    """
    def setZeroes(self, matrix):
        # write your code here
        if not matrix:
            return []
        dicRow = {}
        dicCol = {}
        row = len(matrix)
        column = len(matrix[0])
        for i in range(row):
            for j in range(column):
                if matrix[i][j] == 0:
                    dicRow[i] = True
                    dicCol[j] = True

        for r in dicRow:
            for x in range(column):
                matrix[r][x] = 0

        for c in dicCol:
            for y in range(row):
                matrix[y][c] = 0