Problem of the Day
A new programming or logic puzzle every Mon-Fri

Zero Matrix

Given a multi-dimensional array, loop through each element looking for 0s. When a 0 is found set that entire column and row to 0. The newly updated values don't count toward your search for 0s in the matrix. Here's an example:

//IN
[1,2,0]
[3,4,5]
[6,7,8]

//OUT
[0,0,0]
[3,4,0]
[6,7,0]

Permalink: http://problemotd.com/problem/zero-matrix/

Comments:

  • David - 8 years, 9 months ago

    #include <stdio.h>
#include <stdlib.h>

//I was really tempted at first to generalize this for an N-space matrix
typedef struct {
    int rows;
    int columns;
    int* array;
} matrix2;

void printMatrix(matrix2* m) {
    //No error checking for PotD
    int r, c;

    for(r = 0; r < m->rows; r++) {
        printf("[");
        for(c = 0; c < m->columns; c++) {
            printf("%i", m->array[r*m->columns + c]);
            if(c < m->columns-1) printf(",");
        }
        printf("]\n");
    }
}

void zeroMatrix(matrix2* m) {
    int colToZero[m->columns];
    int rowToZero[m->rows];
    int r, c;

    for(c = 0; c < m->columns; c++)
        colToZero[c] = 0;
    for(r = 0; r < m->rows; r++)
        rowToZero[r] = 0;

    for(r = 0; r < m->rows; r++) {
        for(c = 0; c < m->columns; c++) {
            if(m->array[r*m->columns + c] == 0) {
                colToZero[c] = 1;
                rowToZero[r] = 1;
            }
        }
    }
    for(r = 0; r < m->rows; r++) {
        for(c = 0; c < m->columns; c++) {
            if(colToZero[c] || rowToZero[r]) {
                m->array[r*m->columns +c] = 0;
            }
        }
    }
    printMatrix(m);
}

int main(int argc, char const *argv[])
{
    //This main method is more for testing the functions than being an application
    matrix2* input = (matrix2*) malloc(sizeof(matrix2));    //This cast hides a potential error
    if(input == NULL) {
        printf("Null allocation\n");
        exit(1);
    }
    input->rows = 3;
    input->columns = 3;
    input->array = (int*) malloc(sizeof(int) * input->rows * input->columns);
    if(input->array == NULL) {
        printf("Null allocation\n");
        exit(1);
    }
    input->array[0*3+0] = 1; input->array[0*3+1] = 2; input->array[0*3+2] = 0;
    input->array[1*3+0] = 3; input->array[1*3+1] = 4; input->array[1*3+2] = 5;
    input->array[2*3+0] = 6; input->array[2*3+1] = 7; input->array[2*3+2] = 8;
    //Test printMatrix
    printMatrix(input);
    //Test zeroMatrix
    zeroMatrix(input);



    return 0;
}

    reply permalink

Content curated by @MaxBurstein