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

Advertisements

Pages: 1 2

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.

(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).

Python version

Here’s a solution using Python / Numpy arrays

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