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):
        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)
    
    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 = [1] * len(m[0])
        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[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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: