[Leetcode] 0073. Set Matrix Zeroes

/ Leetcode, Technical Article / By

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

Given an xn 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
  • -2 31 <= matrix[i][j] <= 2 31 - 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?

Table of contents

Python

				
					# time complexity: O(m*n) # space complexity: O(m+n) from typing import List class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: rowSet, colSet = set(), set() for r in range(len(matrix)): for c in range(len(matrix[0])): if matrix[r][c] == 0: rowSet.add(r) colSet.add(c) for r in range(len(matrix)): for c in range(len(matrix[0])): if r in rowSet or c in colSet: matrix[r][c] = 0 matrix = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]] print(Solution().setZeroes(matrix))

related articles