Matrix Fill-In
January 12, 2016
Since we haven’t done one for a while, today’s exercise is an interview question:
Given a matrix of cells containing 0 or 1, modify the matrix so all cells in the same row or column as a cell containing a 1 also contain a 1. For instance, the matrix below left should be converted to the matrix below right:
0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 1 0
Your task is to write a program to fill-in a matrix as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Julia (0.4.1), seemed to work; findn returns the indices for non-zero values; colon is a special index that somehow stands for the whole range in that position; the assigned 1 ends up in every cell in the row or column.
function mfi(A) for (r,k) in findn(A) A[r,:] = 1 A[:,k] = 1 end end(Happy new year!)
Since we have a boolean matrix, let’s represent it with a Python big integer (which for an NxM matrix we can think of as an N-digit number in radix 2**N – and it’s convenient to take row 0 to be the least significant digit etc). It’s interesting that the fillin function doesn’t use the number of rows except to calculate the magic multiplier (which is eg. 0b100001000010000100001 for M = N = 5).
def fillin(n,M,N): radix = 2**M magic = ((2**(M*N))-1)/(radix-1) cols = 0; row = 0; cdigit = radix-1 while n > 0: d = n%radix row |= d if d: cols += cdigit n /= radix; cdigit *= radix return (row * magic) | cols def printmatrix(n,M,N): radix = 2**M for i in range(N): print ('{0:0{1}b}'.format(n%radix,M)) n /= radix def test(m,M,N): p = lambda m: printmatrix(m,M,N) f = lambda m: fillin(m,M,N) print(bin(m)+":"); p(m); print; p(f(m)); print test(int('10000000100000000000',2),5,5) test(int('10000000100000000000',2),6,4)Python version
def fill(m): r = [1] * len(m[0]) c = [int(any(col)) for col in zip(*m)] m[:] = [r if any(row) else c for row in m]Here’s a solution using Python / Numpy arrays
def fill(m): m |= (m.any(axis=0) | m.any(axis=1, keepdims=True)) #test: m = np.array([ [0,0,0,0,0], [0,0,0,0,0], [0,0,0,1,0], [1,0,0,0,0], [0,0,0,0,0]]) fill(m) print(m)Output:
Java Code to populate and manipulate the matrix:-
public class MatrixFillIn {
int[][] matrix = new int[5][5];
public void populateMatrix() {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (i == 0 & j == 0 || i == 2 & j == 4)
// if (i == 3 & j == 0)
matrix[i][j] = 1;
}
}
}
public void printMatrix() {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
System.out.print(matrix[i][j]);
}
System.out.println("");
}
}
public void rearrangeMatrix() {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (matrix[i][j] == 1) {
matrix[i][j] = 2;
// for given i, all js are marked as 1 and added entry
for (int k = 0; k < 5; k++) {
if (matrix[i][k] == 0)
matrix[i][k] = 2;
}
// for given j, all is are marked as 1 and added entry
for (int l = 0; l < 5; l++) {
if (matrix[l][j] == 0)
matrix[l][j] = 2;
}
}
}
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (matrix[i][j] == 2) {
matrix[i][j] = 1;
}
}
}
}
public static void main(String args[]) {
MatrixFillIn m = new MatrixFillIn();
m.populateMatrix();
m.printMatrix();
m.rearrangeMatrix();
m.printMatrix();
}
}
======
I'll really appreciate is someone could improve the complexity of this algorithm. currently it is 2n^2
Java Script. Works under any browser
// Initial matrix 5×5
var matrix1 = [ [0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,1,0],
[1,0,0,0,0],
[0,0,0,0,0]];
// Empty matrix 5×5. Result will be here
var matrix2 = [ [0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0]];
// correct matrix printing function
function print(matrixName) {
for(i=0;i<5;i++) {
for(j=0;j<5; j++){
document.write (matrixName[i][j] + " ");
};
document.write("”);
};
}; // end of function
// Print initial matrix
document.write(“”+”Initial matrix”+”” );
print (matrix1);
// main processing
for(var row=0; row < 5; row++) {
for(var column=0; column < 5; column++){
if (matrix1[row][column] == 1) {
//cycle for "1" adding to rows and columns
for(var i=0; i < 5; i++) {
matrix2[row][i] = 1;
matrix2[i][column] = 1;
};
};
}; // columns cycle
}; //rows cycle
// Print Final marix
document.write("”+”Final result”+”” );
print (matrix2);
===============================================================
You will see Result of program in browser window:
Initial matrix
0 0 0 0 0
0 0 0 0 0
0 0 0 1 0
1 0 0 0 0
0 0 0 0 0
Final result
1 0 0 1 0
1 0 0 1 0
1 1 1 1 1
1 1 1 1 1
1 0 0 1 0
In previous code comand ” ” was shown as “”
This comand could not be shown in comments: BR /
// Initial matrix 5×5
var matrix1 = [ [0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,1,0],
[1,0,0,0,0],
[0,0,0,0,0]];
// Empty matrix 5×5. Result will be here
var matrix2 = [ [0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0],
[0,0,0,0,0]];
// correct matrix printing function
function print(matrixName) {
for(i=0;i<5;i++) {
for(j=0;j<5; j++){
document.write (matrixName[i][j] + " ");
};
document.write("<BR/>");
};
}; // end of function
// Print initial marix
document.write("<br/>"+"Initial matrix"+"<br/>" );
print (matrix1);
// main processing
for(var row=0; row < 5; row++) {
for(var column=0; column < 5; column++){
if (matrix1[row][column] == 1) {
//cycle for "1" adding to rows and columns
for(var i=0; i < 5; i++) {
matrix2[row][i] = 1;
matrix2[i][column] = 1;
};
};
}; // columns
}; //rows
// Print Final marix
document.write("<br/>"+"Final result"+"<br/>" );
print (matrix2);