73. Set Matrix Zeroes

29 Dec 73. Set Matrix Zeroes

Posted at 17:29h in Coding by
0 Likes

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?

 

 

Brute force using O(m*n) space: The initial approach is to start with creating another matrix to store the result. From doing that, you’ll notice that we want a way to know when each row and col should be changed to zero. We don’t want to prematurely change the values in the matrix to zero because as we go through it, we might change a row to 0 because of the new value.

More optimized using O(m + n) space: To do better, we want O(m + n). How do we go about that? Well, we really just need a way to track if any row or any col has a zero, because then that means the entire row or col has to be zero. Ok, well, then we can use an array to track the zeroes for the row and zeros for the col. Whenever we see a zero, just set that row or col to be True.

Space: O(m + n) for the zeroes_row and zeroes_col array

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        “””
        Do not return anything, modify matrix in-place instead.
        “””
        m = len(matrix)
        n = len(matrix[0])
        zeros_row = [1] * m
        zeros_column = [1] * n
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    zeros_row[i] = 0
                    zeros_column[j] = 0
       
        print(zeros_row)
        print(zeros_column)
        for i in range(m):
            for j in range(n):
                if zeros_row[i] == 0  or zeros_column[j] == 0 :
                    matrix[i][j] = 0
No Comments

Post A Comment