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