Microsoft Interview: transforming a matrix

Question

Given a matrix of size n x m filled with 0's and 1's

e.g.:

1 1 0 1 0

0 0 0 0 0

0 1 0 0 0

1 0 1 1 0

if the matrix has 1 at (i,j), fill the column j and row i with 1's

i.e., we get:

1 1 1 1 1

1 1 1 1 0

1 1 1 1 1

1 1 1 1 1

Required complexity: O(n*m) time and O(1) space

NOTE: you are not allowed to store anything except '0' or '1' in the matrix entries

Above is a Microsoft Interview Question.

I thought for two hours now. I have some clues but can't proceed any more.

---

Ok. The first important part of this question is that Even using a straight forward brute-force way, it can't be easily solved.

If I just use two loops to iterate through every cell in the matrix, and change the according row and column, it can't be done as the resulting matrix should be based on the origin matrix.

For example, if I see a[0][0] == 1, I can't change row 0 and column 0 all to 1, because that will affect row 1 as row 1 doesn't have 0 originally.

---

The second thing I noticed is that if a row r contains only 0 and a column c contains only 0, then a[r][c] must be 0; for any other position which is not in this pattern should be 1.

Then another question comes, if I find such a row and column, how can I mark the according cell a[r][c] as special as it already is 0.

---

My intuitive is that I should use some kind of bit operations on this. Or to meet the required complexity, I have to do something like After I take care of a[i][j], I should then proceed to deal with a[i+1][j+1], instead of scan row by row or column by column.

Even for brute-force without considering time complexity, I can't solve it with the other conditions.

Any one has a clue?

---

Solution: Java version

@japreiss has answered this question, and his/her answer is smart and correct. His code is in Python, and now I give the Java version. Credits all go to @japreiss

public class MatrixTransformer {

    private int[][] a;
    private int m;
    private int n;
    
    public MatrixTransformer(int[][] _a, int _m, int _n) {
        a = _a;
        m = _m;
        n = _n;
    }
    
    private int scanRow(int i) {
        int allZero = 0;
        for(int k = 0;k < n;k++)
            if (a[i][k] == 1) {
                allZero = 1;
                break;
            }
        
        return allZero;
    }
    
    private int scanColumn(int j) {
        int allZero = 0;
        for(int k = 0;k < m;k++)
            if (a[k][j] == 1) {
                allZero = 1;
                break;
            }
        
        return allZero;
    }
    
    private void setRowToAllOnes(int i) {
        for(int k = 0; k < n;k++)
            a[i][k] = 1;
    }
    
    private void setColToAllOnes(int j) {
        for(int k = 0; k < m;k++)
            a[k][j] = 1;
    }
        
//  # we're going to use the first row and column
//  # of the matrix to store row and column scan values,
//  # but we need aux storage to deal with the overlap
//  firstRow = scanRow(0)
//  firstCol = scanCol(0)
//
//  # scan each column and store result in 1st row - O(mn) work
    
        
        
    public void transform() {
        int firstRow = scanRow(0);
        int firstCol = scanColumn(0);
                
                
        for(int k = 0;k < n;k++) {
            a[0][k] = scanColumn(k);
        }

        // now row 0 tells us whether each column is all zeroes or not
        // it's also the correct output unless row 0 contained a 1 originally

        for(int k = 0;k < m;k++) {
            a[k][0] = scanRow(k);
        }
        
        a[0][0] = firstCol | firstRow;
        
        for (int i = 1;i < m;i++)
            for(int j = 1;j < n;j++)
                a[i][j] = a[0][j] | a[i][0];


        
        if (firstRow == 1) {
            setRowToAllOnes(0);
        }
        
        if (firstCol == 1) 
            setColToAllOnes(0);
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i< m;i++) {
            for(int j = 0;j < n;j++) {
                sb.append(a[i][j] + ", ");
            }
            sb.append("\n");
        }
        
        return sb.toString();
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        int[][] a = {{1, 1, 0, 1, 0}, {0, 0, 0, 0, 0},{0, 1, 0, 0, 0},{1, 0, 1, 1, 0}};
        MatrixTransformer mt = new MatrixTransformer(a, 4, 5);
        mt.transform();
        System.out.println(mt);
    }

}

Answer 1

Here is a solution in python pseudocode that uses 2 extra bools of storage. I think it is more clear than I could do in English.

def scanRow(i):
    return 0 if row i is all zeroes, else 1

def scanColumn(j):
    return 0 if col j is all zeroes, else 1

# we're going to use the first row and column
# of the matrix to store row and column scan values,
# but we need aux storage to deal with the overlap
firstRow = scanRow(0)
firstCol = scanCol(0)

# scan each column and store result in 1st row - O(mn) work
for col in range(1, n):
    matrix[0, col] = scanColumn(col)

# now row 0 tells us whether each column is all zeroes or not
# it's also the correct output unless row 0 contained a 1 originally

# do the same for rows into column 0 - O(mn) work
for row in range(1, m):
    matrix[row, 0] = scanRow(row)

matrix[0,0] = firstRow or firstCol

# now deal with the rest of the values - O(mn) work
for row in range(1, m):
    for col in range(1, n):
        matrix[row, col] = matrix[0, col] or matrix[row, 0]


# 3 O(mn) passes!

# go back and fix row 0 and column 0
if firstRow:
    # set row 0 to all ones

if firstCol:
    # set col 0 to all ones