Set Matrix Zeroes Solutions in C++

// Source : https://oj.leetcode.com/problems/set-matrix-zeroes/
// Author : Hao Chen
// Date   : 2014-06-23



class Solution {
public:
    Solution(){
        srand(time(NULL));
    }
    void setZeroes(vector<vector<int> > &matrix) {
        if(random()%2){
            setZeroes1(matrix);
        }
        setZeroes2(matrix);
    }
    
    void setZeroes1(vector<vector<int> > &matrix) {
        
        int bRow = false, bCol=false;
        
        for (int r=0; r<matrix.size(); r++){
            for(int c=0; c<matrix[r].size(); c++){
                if (matrix[r][c]==0){
                    if (r==0) bRow = true;
                    if (c==0) bCol = true;
                    matrix[0][c] = matrix[r][0] = 0;
                }
            }
        }
        
        for (int r=1; r<matrix.size(); r++){
            for(int c=1; c<matrix[r].size(); c++){
                if (matrix[0][c]==0 || matrix[r][0]==0) {
                    matrix[r][c]=0;
                }
            }
        }
        if (bRow){
            for(int c=0; c<matrix[0].size(); c++) matrix[0][c] = 0;
        }
        if (bCol){
            for(int r=0; r<matrix.size(); r++) matrix[r][0] = 0;
        }

    }
    
    void setZeroes2(vector<vector<int> > &matrix) {

        bool *row = new bool[matrix.size()]();
        bool *col = new bool[matrix[0].size()]();
        for (int r=0; r<matrix.size(); r++){
            for(int c=0; c<matrix[r].size(); c++){
                if (matrix[r][c]==0){
                    row[r]=true;
                    col[c]=true;
                }
            }
        }
        
        for (int r=0; r<matrix.size(); r++){
            for(int c=0; c<matrix[r].size(); c++){
                if (row[r] || col[c]) {
                    matrix[r][c]=0;
                }
            }
        }
    }
};

#include <vector>
using std::vector;

class Solution {
public:
    void setZeroes(vector<vector<int> > &matrix) {
        bool bFirstColZero = false;
        auto rows = matrix.size(), cols = matrix[0].size();
        
        for (decltype(rows) i=0; i<rows; ++i) {
            if (matrix[i][0] == 0) bFirstColZero = true;
            for (decltype(cols) j=1; j<cols; ++j)
                if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;
        }
        
        for (int i=rows-1; i>=0; --i) {
            for (int j=cols-1; j>0; --j)
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            if (bFirstColZero) matrix[i][0] = 0;
        }
    }
};

/// Source : https://leetcode.com/problems/set-matrix-zeroes/description/
/// Author : liuyubobobo
/// Time   : 2018-10-05

#include <iostream>
#include <vector>

using namespace std;


/// Using another matrix to record zero place
/// Time Complexity: O(m * n * (m + n))
/// Space Complexity: O(m * n)
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {

        int m = matrix.size();
        if(!m) return;

        int n = matrix[0].size();
        if(!n) return;

        vector<vector<bool>> isZero(m, vector<bool>(n, false));
        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                if(!matrix[i][j]){
                    for(int k = 0; k < n; k ++)
                        isZero[i][k] = true;
                    for(int k = 0; k < m; k ++)
                        isZero[k][j] = true;
                }

        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                if(isZero[i][j])
                    matrix[i][j] = 0;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/set-matrix-zeroes/description/
/// Author : liuyubobobo
/// Time   : 2018-10-05

#include <iostream>
#include <vector>

using namespace std;


/// Only record the zero row index and col index
/// Time Complexity: O(m * n)
/// Space Complexity: O(m + n)
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {

        int m = matrix.size();
        if(!m) return;

        int n = matrix[0].size();
        if(!n) return;

        vector<int> zeroRows, zeroCols;
        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                if(!matrix[i][j]){
                    zeroRows.push_back(i);
                    zeroCols.push_back(j);
                }

        for(int r: zeroRows)
            for(int j = 0; j < n; j ++)
                matrix[r][j] = 0;

        for(int c: zeroCols)
            for(int i = 0; i < m; i ++)
                matrix[i][c] = 0;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/set-matrix-zeroes/description/
/// Author : liuyubobobo
/// Time   : 2018-10-05

#include <iostream>
#include <vector>

using namespace std;


/// Using an sentinel value to mark zero in place
/// Attention: this method is actually wrong since we can not guarantee that
///            the sentinel value can not occur in the matrix
///
/// Time Complexity: O(m * n * (m + n))
/// Space Complexity: O(1)
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {

        int m = matrix.size();
        if(!m) return;

        int n = matrix[0].size();
        if(!n) return;

        int sentinel = 2e9;
        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                if(matrix[i][j] == 0){
                    for(int k = 0; k < n; k ++)
                        if(matrix[i][k] != 0)
                            matrix[i][k] = sentinel;
                    for(int k = 0; k < m; k ++)
                        if(matrix[k][j] != 0)
                            matrix[k][j] = sentinel;
                }

        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                if(matrix[i][j] == sentinel)
                    matrix[i][j] = 0;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/set-matrix-zeroes/description/
/// Author : liuyubobobo
/// Time   : 2018-10-05

#include <iostream>
#include <vector>

using namespace std;


/// Make a marker in the first element of every row and column
/// Time Complexity: O(m * n)
/// Space Complexity: O(1)
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {

        int m = matrix.size();
        if(!m) return;

        int n = matrix[0].size();
        if(!n) return;

        bool zeroIndexColZero = false;
        for(int i = 0; i < m; i ++)
            for(int j = 0; j < n; j ++)
                if(!matrix[i][j]){
                    matrix[i][0] = 0;
                    if(j == 0)
                        zeroIndexColZero = true;
                    else
                        matrix[0][j] = 0;
                }

        for(int i = 1; i < m; i ++)
            if(!matrix[i][0])
                for(int j = 0; j < n; j ++)
                    matrix[i][j] = 0;

        for(int j = 1; j < n; j ++)
            if(!matrix[0][j])
                for(int i = 0; i < m; i ++)
                    matrix[i][j] = 0;

        if(!matrix[0][0])
            for(int j = 0; j < n; j ++)
                matrix[0][j] = 0;

        if(zeroIndexColZero)
            for(int i = 0; i < m; i ++)
                matrix[i][0] = 0;
    }
};


void print_matrix(const vector<vector<int>>& matrix){

    for(const vector<int>& row: matrix){
        for(int e: row)
            cout << e << " ";
        cout << endl;
    }
    cout << endl;
}

int main() {

    vector<vector<int>> matrix1 = {
            {1,1,1},{1,0,1},{1,1,1}
    };
    Solution().setZeroes(matrix1);
    print_matrix(matrix1);

    vector<vector<int>> matrix2 = {
            {0,1,2,0},{3,4,5,2},{1,3,1,5}
    };
    Solution().setZeroes(matrix2);
    print_matrix(matrix2);

    return 0;
}