LC 73 - Set Matrix Zeroes

Question

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?

Links

Question here and solution here

Solution

concept

We will keep two arrays row and col to keep track which row and col should be marked. We will then run through the matrix again to put the cell to 0 according to these 2 arrays.

The more space optimized way ($O(1)$ space) is the store the array directly in the matrix itself. This works due to the order we are iterating through the matrix (left -> right, top -> bottom) so that we can overwrite these cells. The only cell we need to take care is the overlap (top left cell), and we need to save that cell at a variable.

code

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        
        O(m + n) space complexity
        """
        ROWS, COLS = len(matrix), len(matrix[0])
        row = [False] * ROWS
        col = [False] * COLS

        for r in range(ROWS):
            for c in range(COLS):
                if matrix[r][c] == 0:
                    row[r] = True
                    col[c] = True
    
        for r in range(ROWS):
            for c in range(COLS):
                if row[r] or col[c]:
                    matrix[r][c] = 0
                    
class Solution:
	    """
        Do not return anything, modify matrix in-place instead.
        
        O(1) space complexity
        """
    def setZeroes(self, matrix: List[List[int]]) -> None:
        ROWS, COLS = len(matrix), len(matrix[0])
        rowZero = False # handle top left cell, this cell marks the top row

        for r in range(ROWS):
            for c in range(COLS):
                if matrix[r][c] == 0:
                    matrix[0][c] = 0 # mark the col zero
                    if r > 0: # only mark row zero if it is not first row
                        matrix[r][0] = 0
                    else: # first row is zero
                        rowZero = True
		# change most row and col to zero
		# except for the frist row and col
        for r in range(1, ROWS):
            for c in range(1, COLS):
                if matrix[0][c] == 0 or matrix[r][0] == 0:
                    matrix[r][c] = 0
		# handle first col
        if matrix[0][0] == 0:
            for r in range(ROWS):
                matrix[r][0] = 0
		# handle first row
        if rowZero:
            for c in range(COLS):
                matrix[0][c] = 0

Complexity

time: $O(mn)$
space: $O(m + n)$ or $O(1)$