Algorithm to modify a matrix and set columns and rows to zero

Question

This is technically a code challenge. I was asked an interesting question at an interview and am hoping for some insight as the best answer I could come up with was O(2n^2) - n-squared category, but still pretty much brute force.

Let's say you have a matrix that's M by N size ( an array of arrays (int[][]) )

1 2 4 3 1
0 5 3 7 7
5 8 9 2 8
6 7 0 8 9

If a cell contains a Zero, then set that entire row and column to zero.
Making the result:

0 2 0 3 1
0 0 0 0 0 
0 8 0 2 8
0 0 0 0 0 

What is the fastest and/or best way to do this?

---

My own answer is to iterate the entire array of arrays, keep track of rows and columns to zero out, and then zero them out.

public void zeroOut(int[][] myArray){
    ArrayList<Integer> rowsToZero = new....
    ArrayList<Integer> columnsToZero = new....

    for(int i=0; i<myArray.length; i++){ // record which rows and columns will be zeroed
        for(int j=0; j<myArray[i].length; i++){
            if(myArray[i][j] == 0){
                if(!rowsToZero.contains(i)) rowsToZero.add(i);
                if(!columnsToZero.contains(j)) columnsToZero.add(j);
            }
        }
    }
    for(int row : rows){ // now zero the rows
        myArray[row] = int[myArray.length];
    }

    for(int i=0; i<myArray.length; i++){
        for(int column: columns){ // now zero the columns
            myArray[i][column] = 0;
        }    
    }
}

Is there a better algorithm? Is there a better data-structure to represent this matrix?

Answer 1

you can do this by taking two int but the only condition is the no of rows and cols should less than or equal to 32. You can do the same with greater than 32 but you have to take array of ints.

So the logic is :

• take two ints i.e. row and col
• traverse the matrix if matrix[i][j] = 0 than set the corresponding bits in the row and col
• after traversal traverse again and set the matrix[i][j] = 0 if corresponding bit of either row or column is set.

The time complexity is same O(N^2) but it is memory efficient. Please find my code below .

---

Check whether the array[row][col] == 0 if 0 than set the corresponding bit in r and c.

        int r = 0, c = 0;
        for (int row = 0; row < 5; row++) {
            for (int col = 0; col < 7; col++) {
                if (array[row][col] == 0) {
                    r = r | (1<<row);
                    c = c | (1<<col);
                }
            }
        }

Now if either of the bit is set than make the cell to 0.

  for (int row = 0; row < 5; row++) {
        for (int col = 0; col <7; col++) {
            if (((c&(1<<col))!=0) || ((r&(1<<row))!=0)) {
                array[row][col] = 0;  
            }
        }
    }