A matrix on n*n size is given with 0s and 1s as values. Wherever a 1 is present make the complete row and column of that element equal to 1. At the end tell how many 1s are present till the complete operation is completed.
Given a 2-dimensional boolean matrix mat of size N x M, modify the matrix such that if an element is 1, set its entire row and column to 1 i.e. if mat[i][j] = 1, then make all the elements of the ith row and the jth column as 1.

Note :

You need to make the modifications in the input matrix. You do not need to print anything, it has already been taken care of.

Input Format

The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow. The first line of each test case contains two single-spaced integers N and M, representing the number of rows and columns of the matrix respectively. The next N line contains M single-spaced elements (0 or 1).

Output Format:

For each test case, the modified matrix is printed. The output for each test case is in a separate line.

Constraints:

1

Question

A matrix on n*n size is given with 0s and 1s as values. Wherever a 1 is present make the complete row and column of that element equal to 1. At the end tell how many 1s are present till the complete operation is completed.

Given a 2-dimensional boolean matrix mat of size N x M, modify the matrix such that if an element is 1, set its entire row and column to 1 i.e. if mat[i][j] = 1, then make all the elements of the ith row and the jth column as 1.

Note :

You need to make the modifications in the input matrix.

You do not need to print anything, it has already been taken care of.

Input Format

The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The first line of each test case contains two single-spaced integers N and M, representing the number of rows and columns of the matrix respectively.

The next N line contains M single-spaced elements (0 or 1).

Output Format:

For each test case, the modified matrix is printed.

The output for each test case is in a separate line.

Constraints:

1 <= T <= 10
1 <= N, M <= 200

Where N and M are the number of rows and columns respectively.

Accepted Answer

To do it in minimum time complexity, start from first index, maintain 2 variables of number of of columns and number of rows completely made 1 till now. maintain a variable num=0. Now whenever a 1 is encountered add n -num_column and n-num_row to num and also increment num_row and num_col.

Accepted Answer

Using additional space

The main idea behind this approach is that we use two temporary arrays, row[N] and col[M], to keep a track of the rows and columns which should be set to 1. Initially, both the arrays are initialized as 0.

Now, we traverse the given matrix and whenever we find a cell Mat[i][j] with value 1, we set row[i] = 1 and col[j] = 1.

After this traversal, we again traverse the given matrix and for each cell Mat[i][j], we check if either of row[i] or col[j] is 1. If either of the two values is 1, we set the value of the cell in the given matrix to 1.

Space Complexity: O(1)Explanation:

O(N + M), where N and M are the number of rows and columns in the given matrix respectively.

This approach requires two temporary arrays, row and col, of sizes N and M respectively. Also, we are making the modifications in the input matrix itself, so no additional space is required on that end. Thus, the final space complexity is O(N + M).

Time Complexity: O(1)Explanation:

O(N * M), where N and M are the number of rows and columns in the given matrix respectively.

The traversal of the matrix takes O(N * M) time. Since we are traversing the matrix two times, the final complexity is O(2 * N * M) = O(N * M).

Accepted Answer

Space Optimized Approach

The idea behind this approach is to make the solution space efficient by using the first cell of every row and column as a flag. This flag would determine whether the row or column should be set to 1. The algorithm for this approach is as follows :

We iterate over the given matrix and mark the first cell of a row i and first cell of a column j as 1, if Mat[i][j] = 1.

But, the thing to note here is that the first cell of row and column for the first row and first column is the same i.e. Mat[0][0]. Hence, we use an additional variable, setCol, to tell us if the first column should be set to 1 or not and Mat[0][0] would be used to tell the same for the first row.

The same is shown below:

for (int i = 0; i < N; i++) {

// Since first cell for both first row and first column is the same i.e. matrix[0][0]

// We can use an additional variable setCol for the first column.

if (Mat[i][0] == 1) {

isCol = true;

}

for (int j = 1; j < M; j++) {

// If an element is 1, we set the first element of the corresponding row and column to 0

if (Mat[i][j] == 1) {

Mat[0][j] = 1;

Mat[i][0] = 1;

}

Now, we again iterate over the original matrix starting from the second row and second column i.e. Mat[1][1] onwards. For every cell we check if its row or column has been marked earlier by checking the respective first row cell or first column cell. If any of them was marked, we set the value in the cell to 1.
We then check if Mat[0][0] == 1, if this is the case, we mark the first row as 1.
And finally, we check if the first column was marked, we make all entries in it as 1.

Space Complexity: O(1)Explanation:

O(1).

No additional space is required in this approach.