[ create a new paste ] login | about

Link: http://codepad.org/fycIyflw    [ raw code | output | fork | 3 comments ]

mdo - C++, pasted on Jun 1:
/*
    Given a matrix of size n x m filled with 0's and 1's
    e.g.:
    1 1 0 1 0
    0 0 0 0 0 
    0 1 0 0 0
    1 0 1 1 0

    if the matrix has 1 at (i,j), fill the column j and row i with 1's
    i.e., we get:
    1 1 1 1 1
    1 1 1 1 0 
    1 1 1 1 1
    1 1 1 1 1

    complexity: O(n*m) time and O(1) space
    NOTE: you are not allowed to store anything except
    '0' or '1' in the matrix entries
*/

#include <stdio.h>

static const int ROWS = 4;
static const int COLS = 5;

void print_array(int arr[][COLS], const int& rows, const int& cols)
{
    for (int j = 0; j < rows; ++j) {
        for (int i = 0; i < cols; ++i)
            printf("%d ", arr[j][i]);
        printf("\n");
    }
    printf("\n");
}

void set_ones(int arr[][COLS], const int& rows, const int& cols)
{
    int curval;

    /* Update the table headers */
    for (int j = 1; j < rows; ++j){
        for (int i = 1; i < cols; ++i){
            curval = arr[j][i];            
            if (1 == curval){
                /* Update the row info */
                arr[j][0] = curval;
                /* Update the column info */
                arr[0][i] = curval;                
            }        
        }
    }

    printf("After headers update\n");
    print_array(arr, rows, cols);

    /* Update the inner matrix */
    for (int j = 1; j < rows; ++j){
        for (int i = 1; i < cols; ++i){
            if (arr[j][0] == 1 || arr[0][i] == 1)
                arr[j][i] = 1;            
        }
    }

    printf("After inner matrix update\n");
    print_array(arr, rows, cols);

    if (arr[0][0] == 1){
        /* Update the inner matrix */
        for (int j = 0; j < rows; ++j){
            for (int i = 0; i < cols; ++i){
                if (j == 0 || i == 0)
                    arr[j][i] = 1;            
            }
        }
    }
    printf("After processing the matrix header\n");
    print_array(arr, rows, cols);
}

int main()
{
    int arr[ROWS][COLS] = { 
        {1, 1, 0, 1, 0},
        {0, 0, 0, 0, 0,}, 
        {0, 1, 0, 0, 0,},
        {1, 0, 1, 1, 0,}
    };

    printf("Original matrix:\n");
    print_array(arr, ROWS, COLS);
    set_ones(arr, ROWS, COLS);

    return 0;
}


Output:
Original matrix:
1 1 0 1 0 
0 0 0 0 0 
0 1 0 0 0 
1 0 1 1 0 

After headers update
1 1 1 1 0 
0 0 0 0 0 
1 1 0 0 0 
1 0 1 1 0 

After inner matrix update
1 1 1 1 0 
0 1 1 1 0 
1 1 1 1 1 
1 1 1 1 1 

After processing the matrix header
1 1 1 1 1 
1 1 1 1 0 
1 1 1 1 1 
1 1 1 1 1 



Create a new paste based on this one


Comments:
posted by mdo on Jun 3
Assuming matrix is 0-based, i.e. the first element is at mat[0][0]

1. Use the first row and first column as table headers to contain column and row info respectively.
1.1 Note the element at mat[0][0]. If it is 1, it will require special handling at the end (described later)

2. Now, start scanning the inner matrix from index[1][1] up to the last element
2.1 If the element at[row][col] == 1 then update the table header data as follows
Row: mat[row][0] = 1;
Column: mat[0][col] = 1;

At this point we have the complete info on which column and row should be set to 1

3. Again start scanning the inner matrix starting from mat[1][1] and set each element
to 1 if either the current row or column contains 1 in the table header:
if ( (mat[row][0] == 1) || (mat[0][col] == 1) ) then set mat[row][col] to 1.

At this point we have processed all the cells in the inner matrix and we are
yet to process the table header itself

4. Process the table header
If the matt[0][0] == 1 then set all the elements in the first column and first
row to 1
5. Done

Time complexity O(2*((n-1)(m-1)+(n+m-1)), i.e. O(2*n*m - (n+m) + 1), i.e. O(2*n*m)
Space O(1)

reply
posted by Aragon on Jul 8
1 doubt for this matrix:

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

your code will convert the header row and column both to 1 due to last check if mat[0][0]==1.
but in solution only 0th row should become 1 not the 0th column.

reply
posted by Aragon on Jul 8
oh sorry got the question wrong.. you code is correct. Thanks

reply