Last Updated: 15 Dec, 2020
Set Matrix Ones
Easy
Asked in company
You have been given a non-empty grid ‘MAT’ consisting of only 0s and 1s. Your task is to modify it in such a way that if a cell has value 1 (MAT[i][j] == 1), then all the cells of the i-th row and j-th column should be changed to 1.
For Example
If the given grid is this:
[0, 0, 0]
[0, 0, 1]
Then the modified grid will be
[0, 0, 1],
[1, 1, 1]
Input Format
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first input line of each test case contains two space integers‘ N’ and ‘M’ representing the number of rows and columns of the grid, respectively.
The next 'N' lines represent the rows of the grid. Every row contains M single space-separated integers.
Output Format
For each test case, print the modified grid.
Print the output of each test case in a separate line.
Note
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Also, update the given matrix in place.
Constraints
1 <= T <= 100
1 <= N <= 50
1 <= M <= 50
0 <= MAT[i][j] <= 1
Time limit: 1 sec
Approaches
We will traverse the whole grid and whenever MAT[i][j] == 1, we will mark all 0s in the i-th row and j-th column as -1. This will help us in differentiating between the 1s that are initially there in the matrix and the 1s which we will set now.
Now, traverse the grid again and mark the cells with value -1 as 1.
We will store the row number and column number of cells having value 1 and then mark all the cells of recorded row and columns as 1 in the next iteration.
Algorithm
- We will create two boolean arrays ‘rows’ and ‘columns’ of size ‘N’ and ‘M’ respectively.
- Now, traverse the whole grid and if MAT[i][j] == 1 then mark:
- rows[i] = true.
- columns[j] = true.
- Now, we will traverse the whole matrix again and if rows[i] == true or columns[j] == true, we will mark MAT[i][j] as 1.
The main idea is that we will use the first cell of every row and column as an indicator that the row or column has any cell with value 1 or not.
We will use two additional variables ‘firstColumn’ to tell us if the first column contains a cell with value 1 or not and ‘firstRow’ would be used to tell the same for the first row.
Algorithm
- We will iterate over the grid and we mark the first cell of row i and first cell of a column j as 1 if MAT[i][j] == 1.
- Now, we will iterate again over the grid and for every cell, we check if the row or column had been marked earlier by checking the respective first-row cell or first column cell. If any of them was marked, we will set the value in the cell to 1.
- We then check if ‘firstRow’ == 1, if this is the case, we will mark all cells of the first row as one.
- And finally, we will check if the variable ‘firstColumn’ is 1, then mark all cells of the first column as 1.