Best algorithm for this interview problem

Question

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

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

results in

0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0

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.

Answer 1

I can do it with two integer variables and two passes (up to 32 rows and columns...)

bool matrix[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}
};

int CompleteRows = ~0;
int CompleteCols = ~0;

// Find the first 0
for (int row = 0; row < 5; ++row)
{
 for (int col = 0; col < 5; ++col)
 {
  CompleteRows &= ~(!matrix[row][col] << row);
  CompleteCols &= ~(!matrix[row][col] << col);
 }
}

for (int row = 0; row < 5; ++row)
 for (int col = 0; col < 5; ++col)
  matrix[row][col] = (CompleteRows & (1 << row)) && (CompleteCols & (1 << col));

Answer 2

You can calculate the new value of each cell by multiplying all values of the matrix' column and row of that cell.

edit: I would not do that destructively, just return a new array.

Answer 3

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.

Answer 4

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)

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

Answer 6

While impossible given the constraints, the most space efficient way to do it is by traversing the matrix in an overlaping, alternating row/column fashion, which would make a pattern similar to laying bricks in a zig-zag fashion:

-----
|----
||---
|||--
||||-

Using this, you would go in each row/column, as indicated, and if you encounter a 0 at any time, set a boolean variable, and re-walk that row/column, setting the entries to 0 as you go.

This will require no extra memory, and will only use one boolean variable. Unfortunately, if the "far" edge is set to all be 0, that is the worst case and you walk the whole array twice.

Answer 7

create a result matrix and set all the values to 1. go through the data matrix as soon as a 0 is encountered, set the result matrix row column to 0

At the end of the first pass, the result matrix will have the correct answer.

Looks pretty simple. Is there a trick I am missing? Are you not allowed to use a result set?

EDIT:

Looks like a F# function, but that is cheating a bit since even though you are doing a single pass, the function can be recursive.

It looks like the interviewer is trying to figure out if you know functional programming.

Answer 8

Based on the result the algorithm is a complex way to say, find all positions where the full row and column are all 1 ?

so any 0 makes its row and column 0 on the target matrix.

Answer 9

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.

Answer 10

Nice challange. This solution sort of uses just two booleans created on the stack, but the booleans are created several times on the stack since the function is recursive.

typedef unsigned short     WORD;
typedef unsigned char      BOOL;
#define true  1
#define false 0
BYTE buffer[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
};
int scan_to_end(BOOL *h,BOOL *w,WORD N,WORD pos_N)
{
    WORD i;
    for(i=0;i<N;i++)
    {
     if(!buffer[i][pos_N])
      *h=false;
     if(!buffer[pos_N][i])
      *w=false;
    }
    return 0;
}
int set_line(BOOL h,BOOL w,WORD N,WORD pos_N)
{
    WORD i;
    if(!h)
     for(i=0;i<N;i++)
      buffer[i][pos_N] = false;
    if(!w)
     for(i=0;i<N;i++)
      buffer[pos_N][i] = false;
    return 0;
}
int scan(int N,int pos_N)
{
    BOOL h = true;
    BOOL w = true;
    if(pos_N == N)
     return 0;
    // Do single scan
    scan_to_end(&h,&w,N,pos_N);
    // Scan all recursive before changeing data
    scan(N,pos_N+1);
    // Set the result of the scan
    set_line(h,w,N,pos_N);
    return 0;
}
int main(void)
{
    printf("Old matrix\n");
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]);
    scan(5,0);
    printf("New matrix\n");
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]);
    printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]);
    system( "pause" );
    return 0;
}

This scans in a pattern like:

s,s,s,s,s
s,0,0,0,0
s,0,0,0,0
s,0,0,0,0
s,0,0,0,0

0,s,0,0,0
s,s,s,s,s
0,s,0,0,0
0,s,0,0,0
0,s,0,0,0

and so on

And then changeing the values in this pattern on return on each of the scan functions. (Bottom up):

0,0,0,0,c
0,0,0,0,c
0,0,0,0,c
0,0,0,0,c
c,c,c,c,c

0,0,0,c,0
0,0,0,c,0
0,0,0,c,0
c,c,c,c,c
0,0,0,c,0

and so on

Answer 11

Another solution that takes two passes, is to accumulate ANDs horizontally and vertically:

1 0 1 1 0 | 0
0 1 1 1 0 | 0
1 1 1 1 1 | 1
1 0 1 1 1 | 0
1 1 1 1 1 | 1
----------+
0 0 1 1 0

I thought I could design such an algorithm using parity bits, Hamming codes or dynamic programming, possibly using those two booleans as a 2-bit number, but I've had no success yet.

Can you please re-check the problem statement with your engineer and let us know? If there is indeed a solution, I want to keep chipping away at the problem.

Answer 12

Keep a single variable to keep track of what all of the rows ANDed together are.

If a row is -1 (all 1s), then make the next row a reference to that variable

If a row is anything but, it's a 0. You can do everything in one pass. Psuedo-code:

foreach (my $row) rows {
     $andproduct = $andproduct & $row;
     if($row != -1) {
        zero out the row
     }  else {
        replace row with a reference to andproduct
     }
}

That should do it, in a single pass -- but there is an assumption here that N is small enough for the CPU to do arithmetic on a single row, else you're going to need to loop over each row to determine if it's all 1s or not, I believe. But given you're asking about algos and not constraining my hardware, I would just start my answer with "Build a CPU that supports N-bit arithmetic..."

Here's one example how it can be done in C. Note I argue that values and arr taken together represent the array, and p and numproduct are my iterator and AND product variables use to implement the problem. (I could have looped over arr with pointer arithmetic to validate my work, but once was enough!)

int main() {
    int values[] = { -10, 14, -1, -9, -1 }; /* From the problem spec, converted to decimal for my sanity */
    int *arr[5] = { values, values+1, values+2, values+3, values+4 };
    int **p;
    int numproduct = 127;

    for(p = arr; p < arr+5; ++p) {
        numproduct = numproduct & **p;
        if(**p != -1) {
            **p = 0;
        } else {
            *p = &numproduct;
        }
    }

    /* Print our array, this loop is just for show */
    int i;
    for(i = 0; i < 5; ++i) {
        printf("%x\n",*arr[i]);
    }
    return 0;
}

This produces 0, 0, 6, 0, 6, which is the result for the given inputs.

Or in PHP, if people think my stack games in C are cheating (I suggest to you that it's not, because I should be able to store the matrix whichever way I please):

<?php

$values = array(-10, 14, -1, -9, -1);
$numproduct = 127;

for($i = 0; $i < 5; ++$i) {
    $numproduct = $numproduct & $values[$i];
    if($values[$i] != -1) {
        $values[$i] = 0;
    } else {
        $values[$i] = &$numproduct;
    }
}

print_r($values);

Am I missing something?

Answer 13

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

Answer 14

Well, I came up with a single-pass, in-place (non-recursive) solution using 4 bools and 2 loop counters. I've not managed to reduce it to 2 bools and 2 ints, but I wouldn't be surprised if it was possible. It does around 3 reads and 3 writes of each cell, and it should be O(N^2) ie. linear in the array size.

Took me a couple of hours to puzzle this one out - I wouldn't want to have to come up with it under the pressure of an interview! If I've made a booboo I'm too tired to spot it...

Um... I'm choosing to define "single-pass" as making one sweep through the matrix, rather than touching each value once! :-)

#include <stdio.h>
#include <memory.h>

#define SIZE    5

typedef unsigned char u8;

u8 g_Array[ SIZE ][ SIZE ];

void Dump()
{
    for ( int nRow = 0; nRow < SIZE; ++nRow )
    {
     for ( int nColumn = 0; nColumn < SIZE; ++nColumn )
     {
      printf( "%d ", g_Array[ nRow ][ nColumn ] );
     }
     printf( "\n" );
    }
}

void Process()
{
    u8 fCarriedAlpha = true;
    u8 fCarriedBeta = true;
    for ( int nStep = 0; nStep < SIZE; ++nStep )
    {
     u8 fAlpha = (nStep > 0) ? g_Array[ nStep-1 ][ nStep ] : true;
     u8 fBeta = (nStep > 0) ? g_Array[ nStep ][ nStep - 1 ] : true;
     fAlpha &= g_Array[ nStep ][ nStep ];
     fBeta &= g_Array[ nStep ][ nStep ];
     g_Array[ nStep-1 ][ nStep ] = fCarriedBeta;
     g_Array[ nStep ][ nStep-1 ] = fCarriedAlpha;
     for ( int nScan = nStep + 1; nScan < SIZE; ++nScan )
     {
      fBeta &= g_Array[ nStep ][ nScan ];
      if ( nStep > 0 )
      {
       g_Array[ nStep ][ nScan ] &= g_Array[ nStep-1 ][ nScan ];
       g_Array[ nStep-1][ nScan ] = fCarriedBeta;
      }

      fAlpha &= g_Array[ nScan ][ nStep ];
      if ( nStep > 0 )
      {
       g_Array[ nScan ][ nStep ] &= g_Array[ nScan ][ nStep-1 ];
       g_Array[ nScan ][ nStep-1] = fCarriedAlpha;
      }
     }

     g_Array[ nStep ][ nStep ] = fAlpha & fBeta;

     for ( int nScan = nStep - 1; nScan >= 0; --nScan )
     {
      g_Array[ nScan ][ nStep ] &= fAlpha;
      g_Array[ nStep ][ nScan ] &= fBeta;
     }
     fCarriedAlpha = fAlpha;
     fCarriedBeta = fBeta;
    }
}

int main()
{
    memset( g_Array, 1, sizeof(g_Array) );
    g_Array[0][1] = 0;
    g_Array[0][4] = 0;
    g_Array[1][0] = 0;
    g_Array[1][4] = 0;
    g_Array[3][1] = 0;

    printf( "Input:\n" );
    Dump();
    Process();
    printf( "\nOutput:\n" );
    Dump();

    return 0;
}

Answer 15

You can sorta do it in one pass -- if you don't count accessing the matrix in random-access order, which eliminates the benefits of doing it single-pass in the first place (cache-coherence/memory-bandwidth).

[edit: simple, but wrong solution deleted]

You should get better performance than any single-pass method by doing it in two passes: one to accumulate row/column info, and one to apply it. The array (in row-major order) is accessed coherently; for arrays exceeding the cache size (but whose rows can fit in cache), data should be read from memory twice, and stored once:

void fixmatrix2(int M[][], int rows, int cols) {
    bool clearZeroRow= false;
    bool clearZeroCol= false;
    for(int j=0; j < cols; ++j) {
        if( ! M[0][j] ) {
            clearZeroRow= true;
        }
    }
    for(int i=1; i < rows; ++i) { // scan/accumulate pass
        if( ! M[i][0] ) {
            clearZeroCol= true;
        }
        for(int j=1; j < cols; ++j) {
            if( ! M[i][j] ) {
                M[0][j]= 0;
                M[i][0]= 0;
            }
        }
    }
    for(int i=1; i < rows; ++i) { // update pass
        if( M[i][0] ) {
            for(int j=0; j < cols; ++j) {
                if( ! M[j][0] ) {
                    M[i][j]= 0;
                }
            }
        } else {
            for(int j=0; j < cols; ++j) {
                M[i][j]= 0;
            }
        }
        if(clearZeroCol) {
            M[i][0]= 0;
        }
    }
    if(clearZeroRow) {
        for(int j=0; j < cols; ++j) {
            M[0][j]= 0;
        }
    }
}

Answer 16

I'm sure the solution has something to do with recursion. The nice thing about recursion is that it acts like a time machine in that if you set your matrix cell (in this case) to the value of the recursive function, you will be able to set it to a value that you don't find out about until the future, thus enabling you to go back in time, making it so you can do this thing in one pass. Also, you'll be doing your indexing via parameters in the recursive function rather than in for loops.

Answer 17

Okay this is a solution that

• uses just one extra long value for working storage.
• uses no recursion.
• one pass of only N, not even N*N.
• will work for other values of N but will need new #defines.

#include <stdio.h>
#define BIT30 (1<<24)
#define COLMASK 0x108421L
#define ROWMASK 0x1fL

unsigned long long STARTGRID = 
((0x10 | 0x0 | 0x4 | 0x2 | 0x0) << 20) |
((0x00 | 0x8 | 0x4 | 0x2 | 0x0) << 15) |
((0x10 | 0x8 | 0x4 | 0x2 | 0x1) << 10) |
((0x10 | 0x0 | 0x4 | 0x2 | 0x1) << 5) |
((0x10 | 0x8 | 0x4 | 0x2 | 0x1) << 0);


void dumpGrid (char* comment, unsigned long long theGrid) {
    char buffer[1000];
    buffer[0]='\0';
    printf ("\n\n%s\n",comment);
    for (int j=1;j<31; j++) {
     if (j%5!=1)
      printf( "%s%s", ((theGrid & BIT30)==BIT30)? "1" : "0",(((j%5)==0)?"\n" : ",") ); 
     theGrid = theGrid << 1;
    }
}

int main (int argc, const char * argv[]) {
    unsigned long long rowgrid = STARTGRID;
    unsigned long long colGrid = rowgrid;

    unsigned long long rowmask = ROWMASK;
    unsigned long long colmask = COLMASK;

    dumpGrid("Initial Grid", rowgrid);
    for (int i=0; i<5; i++) {
     if ((rowgrid & rowmask)== rowmask) rowgrid |= rowmask;
     else rowgrid &= ~rowmask;
     if ((colGrid & colmask) == colmask) colmask |= colmask;
     else colGrid &=  ~colmask;
     rowmask <<= 5;
     colmask <<= 1;
    }
    colGrid &= rowgrid;
    dumpGrid("RESULT Grid", colGrid);
    return 0;
    }

Answer 18

i hope you enjoy my 1-pass c# solution

you can retrieve an element with O(1) and only need the space of one row and one column of the matrix

bool[][] matrix =
{
    new[] { true, false, true, true, false }, // 10110
    new[] { false, true, true, true, false }, // 01110
    new[] { true, true, true, true, true },   // 11111
    new[] { true, false, true, true, true },  // 10111
    new[] { true, true, true, true, true }    // 11111
};

int n = matrix.Length;
bool[] enabledRows = new bool[n];
bool[] enabledColumns = new bool[n];

for (int i = 0; i < n; i++)
{
    enabledRows[i] = true;
    enabledColumns[i] = true;
}

for (int rowIndex = 0; rowIndex < n; rowIndex++)
{
    for (int columnIndex = 0; columnIndex < n; columnIndex++)
    {
     bool element = matrix[rowIndex][columnIndex];
     enabledRows[rowIndex] &= element;
     enabledColumns[columnIndex] &= element;
    }
}

for (int rowIndex = 0; rowIndex < n; rowIndex++)
{
    for (int columnIndex = 0; columnIndex < n; columnIndex++)
    {
     bool element = enabledRows[rowIndex] & enabledColumns[columnIndex];
     Console.Write(Convert.ToInt32(element));
    }
    Console.WriteLine();
}

/*
    00000
    00000
    00110
    00000
    00110
*/

Answer 19

Ok, I realize that it isn't quite a match, but I got it in one pass using a bool and a byte instead of two bools... close. I also wouldn't vouch for the efficiency of it but these types of questions often require less than optimal solutions.

    private static void doIt(byte[,] matrix)
    {
        byte zeroCols = 0;
        bool zeroRow = false;

        for (int row = 0; row <= matrix.GetUpperBound(0); row++)
        {
            zeroRow = false;
            for (int col = 0; col <= matrix.GetUpperBound(1); col++)
            {
                if (matrix[row, col] == 0)
                {

                    zeroRow = true;
                    zeroCols |= (byte)(Math.Pow(2, col));

                    // reset this column in previous rows
                    for (int innerRow = 0; innerRow < row; innerRow++)
                    {
                        matrix[innerRow, col] = 0;
                    }

                    // reset the previous columns in this row
                    for (int innerCol = 0; innerCol < col; innerCol++)
                    {
                        matrix[row, innerCol] = 0;
                    }
                }
                else if ((int)(zeroCols & ((byte)Math.Pow(2, col))) > 0)
                {
                    matrix[row, col] = 0;
                }

                // Force the row to zero
                if (zeroRow) { matrix[row, col] = 0; }
            }
        }
    }

Answer 20

1 pass, 2 booleans. I just have to assume the integer indexes in the iterations don't count.

This is not a complete solution but I can't get pass this point.

If I could only determine if a 0 is an original 0 or a 1 that was converted to a 0 then I wouldn't have to use -1's and this would work.

My output is like this:

-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

The originality of my approach is using the first half of the examination of a row or column to determine if it contains a 0 and the last half to set the values - this is done by looking at x and width-x and then y and height-y in each iteration. Based on the results of the first half of the iteration, if a 0 in the row or column was found, I use the last half of the iteration to change the 1's to -1's.

I just realized this could be done with only 1 boolean leaving 1 to ...?

I'm posting this hoping someone might say, "Ah, just do this..." (And I spent way too much time on it not to post.)

Here's the code in VB:

Dim D(,) As Integer = {{1, 0, 1, 1, 1}, {0, 1, 1, 0, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {0, 0, 1, 1, 1}}

Dim B1, B2 As Boolean

For y As Integer = 0 To UBound(D)

    B1 = True : B2 = True

    For x As Integer = 0 To UBound(D)

        // Scan row for 0's at x and width - x positions. Halfway through I'll konw if there's a 0 in this row.
        //If a 0 is found set my first boolean to false.
        If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
            If D(x, y) = 0 Or D(UBound(D) - x, y) = 0 Then B1 = False
        End If

        //If the boolean is false then a 0 in this row was found. Spend the last half of this loop
        //updating the values. This is where I'm stuck. If I change a 1 to a 0 it will cause the column
        //scan to fail. So for now I change to a -1. If there was a way to change to 0 yet later tell if
        //the value had changed this would work.
        If Not B1 Then
            If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
                If D(x, y) = 1 Then D(x, y) = -1
                If D(UBound(D) - x, y) = 1 Then D(UBound(D) - x, y) = -1
            End If
        End If

        //These 2 block do the same as the first 2 blocks but I switch x and y to do the column.
        If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
            If D(y, x) = 0 Or D(y, UBound(D) - x) = 0 Then B2 = False
        End If

        If Not B2 Then
            If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then
                If D(y, x) = 1 Then D(y, x) = -1
                If D(y, UBound(D) - x) = 1 Then D(y, UBound(D) - x) = -1
            End If
        End If

    Next
Next

Answer 21

    int[,] A = { 
            { 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 } };

    int i, j;
    int[] r = new int[5]; 
    int[] c = new int[5];


    for(i=0;i<5;i++)
    {
        r[i]=1; c[i]=1;
        for(j=0; j<5; j++)
        {
            r[i]=A[i,j]*r[i];
            c[i]=A[j,i]*c[i];
        }
    }

    for(i=0;i<5;i++)
        for(j=0;j<5;j++)
    A[i,j] = r[i]*r[j];

    for(i=0;i<5;i++)
    {
        for(j=0;j<5;j++)
        {
            Console.Write("{0}\t", A[i,j]);
        }
        Console.WriteLine();
    }