Set Matrix Zeroes

06/28/2016 Array

Question

Given a matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?

A straight forward solution using space is probably a bad idea.

A simple improvement uses space, but still not the best solution.

Could you devise a constant space solution?

Solution

Result: Accepted Time: 40 ms

Here should be some explanations.

void setZeroes(int** matrix, int matrixRowSize, int matrixColSize) {
    int * row = malloc(sizeof(int) * matrixRowSize);
    int * col = malloc(sizeof(int) * matrixColSize);
    memset(row,0,sizeof(int)* matrixRowSize);
    memset(col,0,sizeof(int)* matrixColSize);
    for(int i = 0; i < matrixRowSize; i++)
        for(int j = 0; j < matrixColSize; j++)
            if(!matrix[i][j])
                row[i] = col[j] = 1;
    for(int i = 0; i < matrixRowSize; i++)
        if(row[i])
            for(int j = 0; j < matrixColSize; j++)
                matrix[i][j] = 0;
    for(int j = 0; j < matrixColSize; j++)
        if(col[j])
            for(int i = 0; i < matrixRowSize; i++)
                matrix[i][j] = 0;
    free(row);
    free(col);
}

Complexity Analytics

  • Time Complexity:
  • Space Complexity: