73.md

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.

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?

my thoughts:

1. iterate the matrix, store the idx of '0'. for each stored idx, change col and row to '0's.

2. iterate the matrix, store the idx of col and row of each '0'. change each col and row to '0's.

3. iterate the matrix, when a '0' is found, change the col and row to '#' if the orignial num is not '0'. change all '#' to '0'.

my solution:

**********168 ms
class Solution:
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        col = set()
        row = set()
        w = len(matrix[0])
        h = len(matrix)
        for i in range(h):
            for j in range(w):
                if matrix[i][j] == 0:
                    col.add(j)
                    row.add(i)
                    
        for j in col:
            for i in range(h):
                matrix[i][j] = 0
        for i in row:
            for j in range(w):
                matrix[i][j] = 0
				
**********204 ms, slower but O(1)
class Solution:
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        
        w = len(matrix[0])
        h = len(matrix)
        row = False
        col = False
        for i in range(h):
            if matrix[i][0] == 0:
                col = True
        
        for i in range(w):
            if matrix[0][i] == 0:
                row = True
                
        for i in range(1, h):
            for j in range(1, w):
                if matrix[i][j] == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0
                    
        for i in range(1, h):
            if matrix[i][0] == 0:
                for j in range(1, w):
                    matrix[i][j] = 0
                    
        for j in range(1, w):
            if matrix[0][j] == 0:
                for i in range(1, h):
                    matrix[i][j] = 0
                    
        if col:
            for i in range(h):
                matrix[i][0] = 0
        if row:
            for j in range(w):
                matrix[0][j] = 0

my comments:

from other ppl's solution:

1. Missed this, scan from sec row and sec col, use the first row and col as marker: 
My idea is simple: store states of each row in the first of that row, and store states of each column in the first of that column. Because the state of row0 and the state of column0 would occupy the same cell, I let it be the state of row0, and use another variable “col0” for column0. In the first phase, use matrix elements to set states in a top-down way. In the second phase, use states to set matrix elements in a bottom-up way.

void setZeroes(vector<vector<int> > &matrix) {
    int col0 = 1, rows = matrix.size(), cols = matrix[0].size();

    for (int i = 0; i < rows; i++) {
        if (matrix[i][0] == 0) col0 = 0;
        for (int j = 1; j < cols; j++)
            if (matrix[i][j] == 0)
                matrix[i][0] = matrix[0][j] = 0;
    }

    for (int i = rows - 1; i >= 0; i--) {
        for (int j = cols - 1; j >= 1; j--)
            if (matrix[i][0] == 0 || matrix[0][j] == 0)
                matrix[i][j] = 0;
        if (col0 == 0) matrix[i][0] = 0;
    }
}