0073: Set Matrix Zeroes

Problem Statement

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

You must do it in place.

Example 1:

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

Example 2:

Input: matrix = [[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]]

Constraints:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -231 <= matrix[i][j] <= 231 - 1

Follow up:

  • A straightforward 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?

Code Solution

class Solution:
    def setZeroes(self, matrix):
	    
        nR = len(matrix)
        nC = len(matrix[0])
        
        hasRow0 = False
        hasCol0 = False
        
        m = matrix
        for rx in range(nR):
            if m[rx][0] == 0:
                hasCol0 = True
        
        for cx in range(nC):
            if m[0][cx] == 0:
                hasRow0 = True
        
        for rx in range(1, nR):
            for cx in range(1, nC):
                if m[rx][cx] == 0:
                    m[0][cx] = 0
                    m[rx][0] = 0
        
        for rx in range(1, nR):
            if m[rx][0] == 0:
                for cx in range(1, nC):
                    m[rx][cx] = 0
        
        for cx in range(1, nC):
            if m[0][cx] == 0:
                for rx in range(1, nR):
                    m[rx][cx] = 0
        
        if hasRow0:
            for cx in range(nC):
                m[0][cx] = 0
        if hasCol0:
            for rx in range(nR):
                m[rx][0] = 0