Matrix · 134Medium
Set Matrix Zeroes
Given an m x n matrix, if an element is 0 set its entire row and column to 0. You must do it IN PLACE.
Constraints
- m == matrix.length, n == matrix[0].length
- 1 <= m, n <= 200
- -2^31 <= matrix[i][j] <= 2^31 - 1
Examples
The matrix is mutated in place; the result shown is the matrix afterwards. setZeroes([[1,1,1],[1,0,1],[1,1,1]]) -> [[1,0,1],[0,0,0],[1,0,1]] setZeroes([[0,1,2,0],[3,4,5,2],[1,3,1,5]]) -> [[0,0,0,0],[0,4,5,0],[0,3,1,0]] setZeroes([[1]]) -> [[1]] // 1x1, no zero setZeroes([[0]]) -> [[0]] // 1x1, zero setZeroes([[1,2],[3,0]]) -> [[1,0],[0,0]] setZeroes([[0,0],[0,0]]) -> [[0,0],[0,0]] // already all zeroes
Edge cases
- A matrix that is already all zeroes.
- FOLLOW-UP
- Could you devise a constant O(1) space solution?
Show the target complexity (spoiler)
- Naive
- O(m * n) extra space — a full copy of the matrix, or O(m + n) with row and column
- Target
- O(m * n) time, O(1) space — use the first row and column themselves as the marker storage, with two flags for whether they originally held a zero.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/16-matrix/134-set-matrix-zeroes.js ./practice c 134