Lesson 230 of 250
73. Set Matrix Zeroes
NeetCode: Set Matrix Zeroes · LeetCode: 73. Set Matrix Zeroes · Difficulty: Medium
Given an m x n matrix, if a cell is 0, set its entire row and column to 0. Do it in place.
Example
Input: [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output: [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
Input: [[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]]Brute force: copy and zero from the copy
Zeroing while scanning is wrong: a freshly written 0 looks like an original zero and clears too much. Instead, scan a copy of the original and write the zeros into the real matrix. clone() on each row array copies the row, which is enough for an int[][] because the elements are plain int values. For each zero found in the copy, clear its row and column, which costs O(m + n) per zero.
import java.util.Arrays;
class Solution {
public void setZeroes(int[][] matrix) {
int rows = matrix.length;
int cols = rows == 0 ? 0 : matrix[0].length;
int[][] original = new int[rows][];
for (int i = 0; i < rows; i++) {
original[i] = matrix[i].clone();
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (original[i][j] == 0) {
for (int c = 0; c < cols; c++) {
matrix[i][c] = 0;
}
for (int r = 0; r < rows; r++) {
matrix[r][j] = 0;
}
}
}
}
}
}
public class Main {
public static void main(String[] args) {
int[][] a = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
new Solution().setZeroes(a);
System.out.println(Arrays.deepToString(a));
int[][] b = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
new Solution().setZeroes(b);
System.out.println(Arrays.deepToString(b));
int[][] c = {{5}};
new Solution().setZeroes(c);
System.out.println(Arrays.deepToString(c));
}
}[[1, 0, 1], [0, 0, 0], [1, 0, 1]]
[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
[[5]]Time: O(m · n · (m + n)) in the worst case (all zeros). Space: O(m · n) for the copy.
Better: remember zero rows and columns
Only two facts matter: which rows contain a zero and which columns contain a zero. Record them in two boolean arrays in a first pass, then zero every cell whose row or column is flagged in a second pass. This takes O(m · n) time and O(m + n) extra space.
import java.util.Arrays;
class Solution {
public void setZeroes(int[][] matrix) {
int rows = matrix.length;
int cols = rows == 0 ? 0 : matrix[0].length;
boolean[] zeroRow = new boolean[rows];
boolean[] zeroCol = new boolean[cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
zeroRow[i] = true;
zeroCol[j] = true;
}
}
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (zeroRow[i] || zeroCol[j]) {
matrix[i][j] = 0;
}
}
}
}
}
public class Main {
public static void main(String[] args) {
int[][] a = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
new Solution().setZeroes(a);
System.out.println(Arrays.deepToString(a));
int[][] b = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
new Solution().setZeroes(b);
System.out.println(Arrays.deepToString(b));
int[][] c = {{5}};
new Solution().setZeroes(c);
System.out.println(Arrays.deepToString(c));
}
}[[1, 0, 1], [0, 0, 0], [1, 0, 1]]
[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
[[5]]Time: O(m · n). Space: O(m + n).
Optimal: use the first row and column as the markers
The two boolean arrays can be stored inside the matrix: use matrix[i][0] as "row i must be zeroed" and matrix[0][j] as "column j must be zeroed". That overwrites the first row and column, so first remember with two booleans whether they originally contained a zero. The method returns void, as LeetCode requires, and returns early for an empty matrix. Then:
- Scan the inner cells
1..; on a zero, mark its first-column and first-row cell. - Zero every inner cell whose row marker or column marker is
0. - Finally zero the first row and/or first column if their saved booleans say so. This must come last, because it overwrites the markers.
import java.util.Arrays;
class Solution {
public void setZeroes(int[][] matrix) {
int rows = matrix.length;
if (rows == 0 || matrix[0].length == 0) {
return;
}
int cols = matrix[0].length;
boolean firstRowZero = false;
for (int j = 0; j < cols; j++) {
if (matrix[0][j] == 0) {
firstRowZero = true;
}
}
boolean firstColZero = false;
for (int i = 0; i < rows; i++) {
if (matrix[i][0] == 0) {
firstColZero = true;
}
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (firstRowZero) {
for (int j = 0; j < cols; j++) {
matrix[0][j] = 0;
}
}
if (firstColZero) {
for (int i = 0; i < rows; i++) {
matrix[i][0] = 0;
}
}
}
}
public class Main {
public static void main(String[] args) {
int[][] a = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
new Solution().setZeroes(a);
System.out.println(Arrays.deepToString(a));
int[][] b = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
new Solution().setZeroes(b);
System.out.println(Arrays.deepToString(b));
int[][] c = {{5}};
new Solution().setZeroes(c);
System.out.println(Arrays.deepToString(c));
int[][] d = {};
new Solution().setZeroes(d);
System.out.println(Arrays.deepToString(d));
}
}[[1, 0, 1], [0, 0, 0], [1, 0, 1]]
[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
[[5]]
[]Time: O(m · n). Space: O(1).