Set Matrix Zeroes

Set Matrix Zeroes

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

click to show follow up.

» Solve this problem

Idea: Use bitmap
Time complexity: O(mn)
Space complexity: O(max(m, n) / sizeof (int))

class Solution {
public:
    void setZeroes(vector > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int row = matrix.size();
        int col = matrix[0].size();
        
        int s = sizeof(int);
        
        int r = (row + s - 1) / s;
        int c = (col + s - 1) / s;
        int *rm = new int[r];
        int *cm = new int[c];
        memset(rm, 0, r * s);
        memset(cm, 0, c * s);
        
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (!matrix[i][j]) {
                    rm[i / s] |= 1 << (i % s);
                    cm[j / s] |= 1 << (j % s);
                }
            }
        }
        
        
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (rm[i / s] & 1 << (i % s) || cm[j / s] & 1 << (j % s))
                    matrix[i][j] = 0;
            }
        }
        
        delete[] rm;
        delete[] cm;
    }
};