Crossing out bad lines from the binary matrix

Question

We are given square binary matrix with side n.
We will consider any row or column which contains at least one 0 as 'bad'.
Task is to nullify all bad rows and columns.
Task requires to use O(1) of additional memory.

1 1 0     0 0 0
1 1 1  => 1 0 0
1 0 1     0 0 0

Tough thing is, that we cannot nullify bad lines as we discover them during traversal (otherwise we will always end up with zeroed matrix). So I am looking for such a data structure or such a way of data representation, so it could store all info about bad rows and columns while algorithm is iterating through matrix.

I assume we have to stick to binary and we can't set the cells to any other values outside of 0 or 1, correct? — Bernhard Barker, Mar 06 '14 at 17:31
I have no idea what this question is about. What kind of operations are we allowed to use to fix this? — Niklas B., Mar 06 '14 at 17:32
@NiklasB. Sorry, I am not getting your question. We are allowed to alter content of the matrix in any way we want. We have to keep in mind thought that cell size in 1 bit and that any line (row or column) which had 0 in it should turn into line of all zeros. I believe, example in question is pretty self-explanatory. — Dmitri K, Mar 06 '14 at 17:40
@wf34: I believe it is not, since it doesn't explain itself to me. — Niklas B., Mar 06 '14 at 17:42
Pretty sure this is a duplicate of http://stackoverflow.com/questions/10840044/microsoft-interview-transforming-a-matrix, check my answer there. — japreiss, Mar 06 '14 at 18:03

score 3 · Accepted Answer · answered Mar 06 '14 at 18:49

Actually we only need 2n bits to get the answer: we need to know for each row and column if it is good (1) or bad (0). The answer in each cell would be product of the answers for row and column.

Let's store most of that information in the matrix itself: we can use first row to keep records (0 or 1) for all columns but first, first column to keep records for all rows but first, and we need two more bits to keep records for first row and first column.

At first we get those two additional bits (checking first row and first column).

Then find and store records for other rows and columns.

Then calculate resulting bits in all the matrix except for first row and column.

And finally: first row should be nullified if it was bad and kept as it is otherwise, and the same is to be done with the first column.

Bernhard Barker · Answer 2 · 2014-03-07T09:23:50.470

As the first step, look for a 0 in the grid. If we can't find one, we're done.

If we found one, we know that we're supposed to nullify all 1's in the 0's row and column.

So, since we know the final value of all those cells, we could use that row and column as temporary boolean flags for whether the same row or column contains any 0's.

The exact process:

Look through the matrix to find a 0.
Keeping track of the coordinates of the found 0.
Looping over each row and column, checking whether that row or column contains a 0, and setting the flag appropriately.
Then looping over the matrix again and, for each 1 not in the flag row or column, checking whether either the row or the column flag is set, and, if it is, set that 1 to 0.
Then setting all cells in the row and column acting as flags to 0.

This runs in linear time (O(mn) with m rows and n columns) and O(1) space.

Example:

Input:

Then we look for a zero, and let's say we find the top-middle one.

Then we use the top row and middle column as flag for whether the same row / column contains a 0:

Then we loop over the other cells setting the 1's to 0's if the flag row / column is set:

Then we set the flag row and column to 0's:

Then we have our final output:

This would obviously be done in-place, I just separated it out visually for clarity.

score 0 · Answer 3 · answered Mar 07 '14 at 09:24

I have written C++ implementation with helpful answer of Natalya Ginzburg. Just leaving it here in case that it could be useful for somebody.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <time.h> 
#include <unistd.h>

class Matrix {
public:
    Matrix(int n):
            side(n),
            stride( round(n/8+1) ),
            is0RowGood(true),
            is0ColGood(true) {
        printf("%d %d\n", side, stride);
        data = new char[stride*side]; 
        memset(data, 0, stride*side*sizeof(char) );
        if( !data ) {
            printf("alloc problem\n");
            exit(1);
        }
        fill();
        print();
    }

    ~Matrix() {
        if(data)
            delete data;
    }

    void process() {
        for( int j = 0; j < side; ++j ) {
            if(getEl(0, j) == false) {
                is0RowGood = false;
                break;
            }
        }
        for( int i = 0; i < side; ++i ) {
           if(getEl(i, 0) == false) {
                is0ColGood = false;
                break;
            }
        }

        for( int i = 1; i < side; ++i ) {
            for( int j = 1; j < side; ++j ) {
                if(!getEl(i,j)) {
                    setEl(i,0, false);
                    break;
                }
            }
        }

        for( int j = 1; j < side; ++j ) {
            for( int i = 1; i < side; ++i ) {
                if(!getEl(j,i)) {
                    setEl(0, i, false); 
                    break;
                }
            }
        }
        // nullify now
        for( int i = 1; i < side; ++i ) {
            for( int j = 1; j < side; ++j ) {
                if( !getEl(0,j) || !getEl(i,0) )
                {
                    crossRow(i);
                    crossCol(j);
                }
            }
        }

        if(!is0RowGood)
            crossRow(0);
        if(!is0ColGood)
            crossCol(0);

        printf("--\n");
        print();
    }

private:
    void crossRow(int x) {
        for(int i = 0; i < side; ++i ) {
            setEl(x, i, false);
        }
    }

    void crossCol(int x) {
        for(int i = 0; i < side; ++i ) {
            setEl(i, x, false);
        }
    }

    void print() {
        for( int i = 0; i < side; ++i ) {
            for( int j = 0; j < side; ++j ) {
                printf(" %d ", getEl(i,j));
            }
            printf("\n");
        }
    }

    void fill() {
        for( int i = 0; i < side; ++i ) {
            for( int j = 0; j < side; ++j ) {
                usleep(15);
                setEl(i, j, (rand() % 30 == 0) ? 0 : 1);
            }
        }
    }



    bool getEl(int i, int j) {
        int offset = trunc(i/8) + j*stride;
        char byte = data[offset];
        return byte & static_cast<char>(pow(2, i%8));
    }

    bool setEl(int i, int j, bool val) {
        int offset = trunc(i/8) + j*stride;
        if(val)
            data[offset] |= static_cast<char>(pow(2, i%8));
        else
            data[offset] &= static_cast<char>(255-pow(2, i%8));

    }

    bool is0RowGood;
    bool is0ColGood;
    char* data;
    int side;
    int stride;
};

int
main( int argc,
      const char** argv ) {
    if(argc < 2) {
        printf("give n as arg\n");
        exit(1);
    }
    time_t t;
    if(argc == 3)
        t = atoi(argv[2]);
    else {
     t = time(NULL);
     printf("t=%d",t);
    }
    srand (t);
    int n = atoi( argv[1] );
    printf("n=%d\n",n);
    Matrix m(n);
    m.process();
}

Crossing out bad lines from the binary matrix

3 Answers3