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

Pages: 1 2

### 9 Responses to “Matrix Fill-In”

1. Jussi Piitulainen said

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!)

2. matthew said

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):
cols = 0; row = 0; cdigit = radix-1
while n > 0:
row |= d
if d: cols += cdigit
return (row * magic) | cols

def printmatrix(n,M,N):
for i in range(N):

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)
```
```0b10000000100000000000:

00000
00000
00010
10000
00000

10010
10010
11111
11111
10010

0b10000000100000000000:

000000
100000
000000
000010

100010
111111
100010
111111
```
3. Mike said

Python version

```def fill(m):
r =  * len(m)
c = [int(any(col)) for col in zip(*m)]
m[:] = [r if any(row) else c for row in m]
```
4. Mike said

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:

```[[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]]
```
5. Vikas Dhyani said

Java Code to populate and manipulate the matrix:-

public class MatrixFillIn {
int[][] matrix = new int;

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

6. Yuriy V. said

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

7. Yuriy V. said

In previous code comand ” ” was shown as “”

8. Yuriy V. said

This comand could not be shown in comments: BR /

9. Yuriy V. said

// 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);