Set every cell in matrix to 0 if that row or column contains a 0

Given a NxN matrix with 0s and 1s. Set every row that contains a 0 to all 0s and set every column that contains a 0 to all 0s.

For example

results in

A Microsoft Engineer told me that there is a solution that involves no extra memory, just two boolean variables and one pass, so I'm looking for that answer.

BTW, imagine it is a bit matrix, therefore just 1s and 0s are allow to be in the matrix.

Solution 1:

Ok, so I'm tired as it's 3AM here, but I have a first try inplace with exactly 2 passes on each number in the matrix, so in O(NxN) and it is linear in the size of the matrix.

I use 1rst column and first row as markers to know where are rows/cols with only 1's. Then, there are 2 variables l and c to remember if 1rst row/column are all 1's also. So the first pass sets the markers and resets the rest to 0's.

The second pass sets 1 in places where rows and cols where marked to be 1, and resets 1st line/col depending on l and c.

I doubt strongly that I can be done in 1 pass as squares in the beginning depend on squares in the end. Maybe my 2nd pass can be made more efficient...

import pprint

m = [[1, 0, 1, 1, 0],
     [0, 1, 1, 1, 0],
     [1, 1, 1, 1, 1],
     [1, 0, 1, 1, 1],
     [1, 1, 1, 1, 1]]



N = len(m)

### pass 1

# 1 rst line/column
c = 1
for i in range(N):
    c &= m[i][0]

l = 1
for i in range(1,N):
    l &= m[0][i]


# other line/cols
# use line1, col1 to keep only those with 1
for i in range(1,N):
    for j in range(1,N):
        if m[i][j] == 0:
            m[0][j] = 0
            m[i][0] = 0
        else:
            m[i][j] = 0

### pass 2

# if line1 and col1 are ones: it is 1
for i in range(1,N):
    for j in range(1,N):
        if m[i][0] & m[0][j]:
            m[i][j] = 1

# 1rst row and col: reset if 0
if l == 0:
    for i in range(N):
        m [i][0] = 0

if c == 0:
    for j in range(1,N):
        m [0][j] = 0


pprint.pprint(m)

Solution 2:

This cannot be done in one pass since a single bit has an effect on bits before and after it in any ordering. IOW Whatever order you traverse the array in, you may later come accross a 0 which means you have to go back and change a previous 1 to a 0.

Update

People seem to think that by restricting N to some fixed value (say 8) you can solve this is one pass. Well that's a) missing the point and b) not the original question. I wouldn't post a question on sorting and expect an answer which started "assuming you only want to sort 8 things...".

That said, it's a reasonable approach if you know that N is in fact restricted to 8. My answer above answers the original question which has no such retriction.

Solution 3:

So my idea is to use the values in the last row/column as a flag to indicate whether all of the values in the corresponding column/row are 1s.

Using a Zig Zag scan through the entire matrix EXCEPT the final row/column. At each element, you set the value in the final row/column as to the logical AND of itself with the value in the current element. In other words, if you hit a 0, the final row/column will be set to 0. If you it a 1, the value in the final row/column will be 1 only if it was 1 already. In any case set the current element to 0.

When you've finished, your final row/column should have 1s iff the corresponding column/row was filled with 1s.

Do a linear scan through the final row and column and looking for 1s. Set 1s in the corresponding elements in body of the matrix where the final row and column are both 1s.

Coding it will be tricky to avoid off-by-one errors etc but it should work in one pass.

Solution 4:

I've got a solution here, it runs in a single pass, and does all processing "in place" with no extra memory (save for growing the stack).

It uses recursion to delay the writing of zeros which of course would destroy the matrix for the other rows and cols:

#include <iostream>

/**
* The idea with my algorithm is to delay the writing of zeros
* till all rows and cols can be processed. I do this using
* recursion:
* 1) Enter Recursive Function:
* 2) Check the row and col of this "corner" for zeros and store the results in bools
* 3) Send recursive function to the next corner
* 4) When the recursive function returns, use the data we stored in step 2
*       to zero the the row and col conditionally
*
* The corners I talk about are just how I ensure I hit all the row's a cols,
* I progress through the matrix from (0,0) to (1,1) to (2,2) and on to (n,n).
*
* For simplicities sake, I use ints instead of individual bits. But I never store
* anything but 0 or 1 so it's still fair ;)
*/

// ================================
// Using globals just to keep function
// call syntax as straight forward as possible
int n = 5;
int m[5][5] = {
                { 1, 0, 1, 1, 0 },
                { 0, 1, 1, 1, 0 },
                { 1, 1, 1, 1, 1 },
                { 1, 0, 1, 1, 1 },
                { 1, 1, 1, 1, 1 }
            };
// ================================

// Just declaring the function prototypes
void processMatrix();
void processCorner( int cornerIndex );
bool checkRow( int rowIndex );
bool checkCol( int colIndex );
void zeroRow( int rowIndex );
void zeroCol( int colIndex );
void printMatrix();

// This function primes the pump
void processMatrix() {
    processCorner( 0 );
}

// Step 1) This is the heart of my recursive algorithm
void processCorner( int cornerIndex ) {
    // Step 2) Do the logic processing here and store the results
    bool rowZero = checkRow( cornerIndex );
    bool colZero = checkCol( cornerIndex );

    // Step 3) Now progress through the matrix
    int nextCorner = cornerIndex + 1;
    if( nextCorner < n )
        processCorner( nextCorner );

    // Step 4) Finially apply the changes determined earlier
    if( colZero )
        zeroCol( cornerIndex );
    if( rowZero )
        zeroRow( cornerIndex );
}

// This function returns whether or not the row contains a zero
bool checkRow( int rowIndex ) {
    bool zero = false;
    for( int i=0; i<n && !zero; ++i ) {
        if( m[ rowIndex ][ i ] == 0 )
            zero = true;
    }
    return zero;
}

// This is just a helper function for zeroing a row
void zeroRow( int rowIndex ) {
    for( int i=0; i<n; ++i ) {
        m[ rowIndex ][ i ] = 0;
    }
}

// This function returns whether or not the col contains a zero
bool checkCol( int colIndex ) {
    bool zero = false;
    for( int i=0; i<n && !zero; ++i ) {
        if( m[ i ][ colIndex ] == 0 )
            zero = true;
    }

    return zero;
}

// This is just a helper function for zeroing a col
void zeroCol( int colIndex ) {
    for( int i=0; i<n; ++i ) {
        m[ i ][ colIndex ] = 0;
    }
}

// Just a helper function for printing our matrix to std::out
void printMatrix() {
    std::cout << std::endl;
    for( int y=0; y<n; ++y ) {
        for( int x=0; x<n; ++x ) {
            std::cout << m[y][x] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

// Execute!
int main() {
    printMatrix();
    processMatrix();
    printMatrix();
}

Solution 5:

I don't think it's doable. When you're on the first square and its value is 1, you have no way of knowing what the values of the other squares in the same row and column are. So you have to check those and if there's a zero, return to the first square and change its value to zero. I'll recommend doing it in two passes - the first pass gathers information about which rows and columns must be zeroed out (the information is stored in an array, so we're using some extra memory). The second pass changes the values. I know that's not the solution you're looking for, but I think it's a practical one. The constraints given by you render the problem unsolvable.