Zero Matrix

1.8 Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0.

• Brute force here is an obvious solution. My approach is to first scan through the matrix and collecting the indicies into two different arrays [i][j] where it is zero. These arrays I would then sort in nlogn time in order to remove duplicates.

e.g.

i = [1 2 1]
j = [1 0 3]

• This would require me to also remove match indices, which seems needlessly complicated.

• Instead, I'll go with another approach: scan through the matrix, by row. If I come across a zero, Ill break - there is no need to scan the remainder of that row. And then I emit everything in that row = 0.

• I will have a column array, that I keep track of the columns that needed to be zero's out along the way. This column, I would then sort, and remove duplicates. Finally, I'd zero out the columns.

template<const size_t size1, const size_t size2>
void zero_row_column(array<array<int, size1>, size2> &matrix) {
    vector<int> cols;
    for (int i = 0; i < size2; i++) { 
        for (int j = 0; j < size1; j++) { 
            if (matrix[i][j] == 0) {
                // zero out row
                for (int z = 0; z < size1; z++) {
                    matrix[i][z] = 0;
                }
                // store col
                cols.push_back(j);
                // next row
                break;
            }
        }
    }

    unique(cols.begin(), cols.end());

    for (int i = 0; i < cols.size(); i++) {
        for (int j = 0; j < size2; j++) {
            matrix[j][cols.at(i)] = 0;
        }
    }
}

int main()
{
    srand(time(nullptr));
    array<array<int, 10>, 15> matrix;

    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix.at(i).size(); j++) {
            matrix[i][j] = rand() % 70; //[0-9]
        }
    }

    cout << "Matrix:" << endl;
    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix.at(i).size(); j++) {
            cout << setw(2) << matrix[i][j] << " ";
        }
        cout << "\n";
    }

    zero_row_column(matrix);

    cout << "Zero Matrix:" << endl;
    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix.at(i).size(); j++) {
            cout << setw(2) << matrix[i][j] << " ";
        }
        cout << "\n";
    }
}