Set Matrix Zeroes
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
import java.util.Arrays;
class Main {
/*
Given a matrix matrix containing distinct integers,
modify it in-place such that all rows and columns that
contain zeros are set to zeros.
matrix = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
*/
// iterate through the matrix to record the rows and columns that contains 0
// iterate through the recorded rows and columns and set all the elements to 0
// modify the matrix in place
// time: o(m * n)
// space: o(m + n)
public static void setMatrix(int[][] matrix){
int r = matrix.length;
int c = matrix[0].length;
// boolean arrays to record which rows and columns contains 0
boolean[] rHasZeros = new boolean[r];
boolean[] cHasZeros = new boolean[c];
// iterate to record r and c
for(int i = 0; i < r; i++){
for (int j = 0; j < c; j++){
if(matrix[i][j] == 0){
rHasZeros[i] = true;
cHasZeros[j] = true;
}
}
}
// iterate recorded matrix to set elements -> 0
// r
for(int i = 0; i < r; i++){
if(rHasZeros[i]){
for(int j = 0; j < c; j++){
matrix[i][j] = 0;
}
}
}
//c
for(int j = 0; j < c; j++){
if(cHasZeros[j]){
for(int i = 0; i < r; i++){
matrix[i][j] = 0;
}
}
}
}
public static void main(String[] args) {
int[][] input = {
{1, 1, 1},
{1, 0, 1},
{1, 1, 1}
};
setMatrix(input);
for(int[] r: input){
System.out.println(Arrays.toString(r));
}
}
}
Java
INFO