Instantly share code, notes, and snippets.

Embed
What would you like to do?
public class SetMatrixZeros {
public void setZeroes(int[][] matrix) {
if(matrix == null) return;
if(matrix.length == 0) return;
int m = matrix.length;
int n = matrix[0].length;
boolean[] rows = new boolean[m];
boolean[] cols = new boolean[n];
for(int i = 0 ; i < m; i++){
for(int j = 0; j < n; j++){
if(matrix[i][j] == 0){
rows[i] = true;
cols[j] = true;
}
}
}
for(int i = 0; i < m; i++){
if(rows[i]){
for(int j = 0; j < n; j++){
matrix[i][j] = 0;
}
}
}
for(int j = 0; j < n; j++){
if(cols[j]){
for(int i = 0; i < m; i++){
matrix[i][j] = 0;
}
}
}
}
public void setZeroes2(int[][] matrix) {
if(matrix == null) return;
if(matrix.length == 0) return;
int m = matrix.length;
int n = matrix[0].length;
boolean hasZeroOnFirstRow = false;
boolean hasZeroOnFirstColumn = false;
for(int i = 0; i < m; i++){
if(matrix[i][0] == 0){
hasZeroOnFirstColumn = true;
break;
}
}
for(int j = 0; j < n; j++){
if(matrix[0][j] == 0){
hasZeroOnFirstRow = true;
break;
}
}
// step 2, check other cells
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
if(matrix[i][j] == 0){
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// now we set the rows and columns to zeros
// remember that first row and column records the occurrence of zeros
// in matrix[1:m][1:n]. Therefore, we can only use them to change
// the cells in matrix[1:m][1:n]
for(int i = 1; i < m; i++){
if(matrix[i][0] == 0){
for(int j = 1; j < n; j++){
matrix[i][j] = 0;
}
}
}
for(int j = 1; j < n; j++){
if(matrix[0][j] == 0){
for(int i = 1; i < m; i++){
matrix[i][j] = 0;
}
}
}
// do not forget the first row and column
if(hasZeroOnFirstRow){
for(int j = 0; j < n; j++){
matrix[0][j] = 0;
}
}
if(hasZeroOnFirstColumn){
for(int i = 0; i < m; i++){
matrix[i][0] = 0;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment