Devin's Blog

Set Matrix Zeroes

3 min read

TARGET DECK: Leetcode FILE TAGS: Medium

Intuition

  • You could use a HashMap to store those rows and columns which have a zero in them, then iterate over those, but that costs space.
  • Alternatively, set those rows and columns which are effected by a 0 with inf, then change only those rows and columns in the 2nd passthrough.
  • This prevents the issue that when you set something to 0, that 0 is now a candidate to infect the other rows/columns, whereas if you set it as inf or some other placeholder not in the range, you are marking it for deletion.
  • Alternatively, to avoid the issue of the flag you set being within the bounds of matrix[i][j], set the 0th row and 0th column of that respective row and column to 0
  • Then, set the entire row and column to 0 for those rows and columns which have a 0.
  • Then, do the same for the 0th row and column, if it originally had a 0.

Complexity

Runtime

to go through entire matrix and set respective rows and columns to 0.

Space

since we aren’t storing anything, but using the matrix itself as indicators of whether to set that row or column.

Code

Using Just the 0th Row and Column

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        is_zero_row = False
        is_zero_col = False
 
        # Set 0th row and column to 0 for those rows and columns which have a 0, keeping track of whether the 0th row and column itself had a 0.
        for r in range(m):
            for c in range(n):
                if matrix[r][c] == 0:
                    if r == 0:
                        is_zero_row = True
                    if c == 0:
                        is_zero_col = True
                    matrix[r][0] = 0
                    matrix[0][c] = 0
 
        # Set the entire row and column to 0 if the 0th row/column has a 0
        for r in range(1, m):
            for c in range(1, n):
                if matrix[r][0] == 0 or matrix[0][c] == 0:
                    matrix[r][c] = 0
        
        # If the row is 0, set all the columns to 0
        if is_zero_row:
            for c in range(n):
                matrix[0][c] = 0
 
        # If the column is 0, set all the rows to 0
        if is_zero_col:
            for r in range(m):
                matrix[r][0] = 0

Infinity Flag

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        def setRow(c):
            for i in range(n):
                if matrix[r][i] != 0:
                    matrix[r][i] = inf
 
        def setCol(r):
            for i in range(m):
                if matrix[i][c] != 0:
                    matrix[i][c] = inf
 
        for r in range(m):
            for c in range(n):
                if matrix[r][c] == 0:
                    setRow(c)
                    setCol(r)
                    
        for r in range(m):
            for c in range(n):
                if matrix[r][c] == inf:
                    matrix[r][c] = 0

Axillary Set to Store Rows and Columns

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        zero_rows = set()
        zero_cols = set()
        m, n = len(matrix), len(matrix[0])
        for r in range(m):
            for c in range(n):
                if matrix[r][c] == 0:
                    zero_rows.add(r)
                    zero_cols.add(c)
        
        for r in range(m):
            for c in range(n):
                if r in zero_rows or c in zero_cols:
                    matrix[r][c] = 0

Notes

Cards

START Basic Front: Set Matrix Zeroes Back: Set the respective top row and column to 0, or clobber with infinity the elements that should be set to 0.

END

References

Graph View