73. Set Matrix Zeroes

Problem Statement

link: https://leetcode.com/problems/set-matrix-zeroes/ https://leetcode.cn/problems/set-matrix-zeroes/

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:

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

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]]

Solution Approach

Use the matrix’s first row and column as markers to determine which rows and columns should be zeroed.

Algorithm

1. Determine if the first row and column need zeroing using two flags.
2. Mark zeros in the first row and column for cells that are zero in the matrix.
3. Zero out marked rows and columns, then handle the first row and column using the flags.

Implement

    class Solution:
      def setZeroes(self, matrix: List[List[int]]) -> None:
        m, n = len(matrix), len(matrix[0])
        flag_m = any(matrix[i][0] == 0 for i in range(m))
        flag_n = any(matrix[0][j] == 0 for j in range(n))

        for i in range(1, m):
            for j in range(1, n):
                if  matrix[i][j] == 0:
                    matrix[i][0] = 0 
                    matrix[0][j] = 0
        
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
                
        if flag_m:
            for i in range(m):
                matrix[i][0] = 0
        if flag_n:
            for j in range(n):
                matrix[0][j] = 0
  

    
    

Twitter  facebook  Email