# 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";

}

}

Last modified 3yr ago