Convert Matrix - C++ Solution

1. Introduction

In this post, we explore a matrix manipulation problem that often appears in data processing and image manipulation. The challenge is to convert a binary matrix in such a way that if an element at position (i, j) is 0, then all elements in row i and column j are set to 0.

Problem

Given an M × N binary matrix, the task is to change all elements in any row or column containing a 0 to 0. This transformation must be applied to every row and column containing a 0 in the original matrix.

2. Solution Steps

1. First, create two temporary arrays to store the status (0 or 1) of each row and each column.

2. Traverse the matrix and update the status arrays based on the presence of a 0 in rows and columns.

3. Again traverse the matrix and set the matrix cell to 0 if either its row or column has a 0 in the status arrays.

4. This way, only rows and columns that originally had a 0 will be converted entirely to 0s.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to convert matrix as per the problem statement
void convertMatrix(vector<vector<int>>& matrix) {
    int M = matrix.size();
    int N = matrix[0].size();
    vector<int> rowStatus(M, 1), colStatus(N, 1);

    // Store the status of each row and column
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (matrix[i][j] == 0) {
                rowStatus[i] = 0;
                colStatus[j] = 0;
            }
        }
    }

    // Convert matrix cells to 0 based on row and column status
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (rowStatus[i] == 0 || colStatus[j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
}

int main() {
    vector<vector<int>> matrix = {
        {1, 1, 0, 1, 1},
        {1, 1, 1, 1, 1},
        {1, 1, 1, 0, 1},
        {1, 1, 1, 1, 1},
        {0, 1, 1, 1, 1}
    };

    convertMatrix(matrix);

    // Output the converted matrix
    for (const auto& row : matrix) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    return 0;
}

Output:

0 0 0 0 0
0 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 0 0 0 0

Explanation:

The function convertMatrix first creates two arrays to track the presence of 0s in each row and column. It then traverses the matrix again, setting a cell to 0 if its corresponding row or column is marked in the status arrays. This method ensures that only those rows and columns which originally contained a 0 are entirely converted to 0s, as demonstrated with the given inputs.