# Set matrix zeros

I solved this problem in about 11 minutes (with all 50+ test cases passed).

I think most of you already know me by now, and I truly appreciate your advice, but please be brutal and judge me as if I was being interviewed by you.

Question:

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Code:

public void setZeroes(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
boolean[][] flagArr = new boolean[rows][cols];
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
if(matrix[i][j]==0){
flagArr[i][j]=true;
}
}
}
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
if(flagArr[i][j]==true){
/*for rows*/
for(int k=0; k<rows; k++){
matrix[k][j]=0;
}
/*for cols*/
for(int z=0; z<cols; z++){
matrix[i][z]=0;
}
}
}
}
}

-
I see that you have been writing a lot of code involving primitives to implement some algorithms. How about writing your own more object-oriented classes? I think you could learn a lot by writing your own implementation of a weekend / coding challenge (it's never too late to submit an entry!) – Simon Forsberg Mar 9 '14 at 16:06

I think your code is complete, but not the most efficient it could be.

There are two areas where there are inefficiencies:

• there is no need to have a comprehensive row-column flag matrix... you only need two arrays, one for row, one for columns.
• you have very inefficient zeroing of the rows/columns because you will potentially do many cells many times. (for example, if two values in a row are zero, then you will zero that row twice....)

Consider the following changes:

public void setZeroes(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
boolean[] rowzero = new boolean[rows];
boolean[] colzero = new boolean[cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (matrix[r][c] == 0) {
rowzero[r] = true;
colzero[c] = true;
}
}
}
for (int r = 0; r < rows; r++) {
if (rowzero[r]) {
for (int c = 0; c < cols; c++) {
matrix[r][c] = 0;
}
}
}
for (int c = 0; c < cols; c++) {
if (colzero[c]) {
for (int r = 0; r < rows; r++) {
matrix[r][c] = 0;
}
}
}
}


This only zeros out each affected row one time, and it uses much less memory

-
out of curiosity, how old are you? Your amazing style intimidates a 20ish year old guy like myself, and makes me want to run back to the drawing board. I appreciate your ruthless comments; it helps me improve and motivates me. – bazang Mar 9 '14 at 16:33
@bazang come join us in the 2nd monitor chat room ..... – rolfl Mar 9 '14 at 16:35
If I would have spent just a bit longer thinking about it, I probably would have thought about this solution... Well done, performance-monkey! – Simon Forsberg Mar 9 '14 at 16:44

At first when I took a look at your question I was thinking: Why do you first set values in a boolean matrix to true? I quickly realized, "Oh. That's why."

Overall, well done. I like your code. I would have solved it in the same way. Your coding style is consistent, which makes it easy to follow your code, even though I don't agree with the coding style itself.

• Variable naming. flagArr is a matrix and not an (1 diemensional) array. But it would be more helpful to name it to what it is used for rather than what it is. How about zerosFound? i and j I would either name as x and y or col and row.

• Spacing. It's not wrong to have a bit of more space in your lines. Use spaces around < and = and before { etc. Here's what parts of your code looks like when I press Ctrl + Shift + F in Eclipse (which is a key shortcut for auto formatting).

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
flagArr[i][j] = true;
}
}
}


As I said. Good job.

-

11 minutes, nice :) Keep in mind that taking some time to keep the code maintainable after finish also important which could earn you some extra points too on an interview.

A few things you could improve (in the original code):

1. Rename i to row and j to col. It would be easier to read and harder to mistype.

2. if (flagArr[row][col] == true) {


could be simply

if (flagArr[row][col]) {

3. Extract out a few methods for higher abstraction level:

public void setZeroes(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
boolean[][] zeroMatrix = getZeroMatrix(matrix);
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (zeroMatrix[row][col]) {
fillColumn(matrix, col, 0);
fillRow(matrix, row, 0);
}
}
}
}

public boolean[][] getZeroMatrix(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
boolean[][] result = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
result[i][j] = true;
}
}
}
return result;
}

private void fillRow(int[][] matrix, int row, int value) {
int cols = matrix[0].length;
for (int col = 0; col < cols; col++) {
matrix[row][col] = value;
}
}

private void fillColumn(int[][] matrix, int col, int value) {
int rows = matrix.length;
for (int row = 0; row < rows; row++) {
matrix[row][col] = value;
}
}


It's easier to read, it's easier to get an overview what the method does (without the details) and you can still check them if you are interested in. Furthermore, you need to read and understand less code (not the whole original method) if you want to modify just a small part of it.

-

The other answers have good advice: you can consume less memory and time by keeping track of only the information you need, your naming could be improved, you could refactor the problem into smaller methods.

I would add to that one small performance consideration. Think about what this does:

            if(matrix[i][j]==0){
flagArr[i][j]=true;
}


or in the more efficient algorithm:

        if (matrix[r][c] == 0) {
rowzero[r] = true;
colzero[c] = true;
}


I am going to propose a micro-optimization; this might not be justified because (1) your program might already be fast enough overall, (2) this optimization might be in a portion of the program that is not significantly contributing to the total performance cost, and (3) the optimization might actually make things worse; there's no substitute for measuring carefully to find out. All that said, I would be inclined to write these as:

            flagArr[i][j] = (matrix[i][j] == 0);


or

            rowzero[r] |= (matrix[r][c] == 0);
colzero[c] |= (matrix[r][c] == 0);


A common belief amongst programmers is code does work, so if I can conditionally avoid the work the program will be faster. Though this is often true, it is also true that conditions are also work and any time the branch predictor on the chip predicts wrong, your potentially mess up the processor state. It can therefore be a good idea to do "unnecessary" work unconditionally if doing so is extremely cheap, and thereby skip both the cost of the condition and the risk of branch prediction failure. Setting bools to true or false is insanely fast on modern architecture; the work you are trying to save here is the fastest thing you can possibly do. It can therefore in many cases be completely worthwhile to simply do the work unconditionally rather than spending two nanoseconds trying to avoid work that takes one nanosecond.

-
2 questions: is multiplication (for accessing a 2-d array) faster than messing up the branch predictor? Are you sure the internal work of performing a comparison and returning a boolean doesn't involve conditional branching? – Barmar Mar 10 '14 at 15:08
@Barmar: StackOverflow is a question-and-answer site for just such technical questions. Those sound like good questions to post on StackOverflow. – Eric Lippert Mar 10 '14 at 16:43
I intended them as questions about whether this answer really achieves the optimizations it claims to. – Barmar Mar 10 '14 at 16:44
@Barmar: Well then, your first question can be answered by trying it yourself. Write the code both ways, get out a stopwatch, and benchmark it under carefully controlled conditions and then you'll know. Your second question is about an implementation detail of the Java virtual machine; that question will have to be addressed to the manufacturer of the virtual machine you plan to use. – Eric Lippert Mar 10 '14 at 16:46
You're the one making the claim, it seems like you should provide the data to back it up. I'm not a Javaprogrammer, I'm not going to try setting it up just to answer this. – Barmar Mar 10 '14 at 16:49

Your solution is clear, concise, and correct. So far, so good.

The function should be static.

I might fault your code for excessive use of memory, which would probably prompt a follow-up question. @rolfl has pointed out that you could use two one-dimensional arrays. You could do better, with just one boolean to decide whether to zero the current row, and one boolean[] to keep track of the columns that you will zero. (A simple exercise for you.)

It is even possible to do it with two boolean variables (constant space). It's debatable whether such a solution is better than a one-1D-array solution, though, since it probably has worse cache locality.

public static void setZeroes(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;

for (int i = (rows > cols ? rows : cols) - 1; i >= 0; i--) {
boolean zeroRow = false, zeroCol = false;
if (i < cols) {
for (int r = 0; r < i; r++) {
if (matrix[r][i] == 0) {
zeroCol = true;
break;
}
}
}
if (i < rows) {
for (int c = 0; c < i; c++) {
if (matrix[i][c] == 0) {
zeroRow = true;
break;
}
}
}
if (zeroRow) {
for (int c = 0; c < cols; c++) {
matrix[i][c] = 0;
}
}
if (zeroCol) {
for (int r = 0; r < rows; r++) {
matrix[r][i] = 0;
}
}
}
}

-