Set matrix zeros

Question

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;
                    }
                }
            }
        }
    }

Answer 1

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

Answer 2

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.

Two comments:

• 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.

Answer 3

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.

Answer 4

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.

Answer 5

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;
            }
        }
    }
}