Set Matrix Zeroes
Medium · Matrix · Array · Matrix · Hash Table
Problem
If any cell of an m x n matrix is 0, set its entire row and column to 0. Do it in place.
Examples
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]]
Constraints
- 1 <= m, n <= 200
- -2^31 <= matrix[i][j] <= 2^31 - 1
- Modify the matrix in place
Approaches
- Mark rows and columns in sets — time O(m · n), space O(m + n)
Follow-up
Using O(mn) extra space is straightforward, and O(m + n) is an improvement. Can you do it with only constant extra space?
Related problems
Start free on Cariara · Coding problems · System design studio
