# Find the Good Matrix

#### You have given a 2-dimensional array ‘ARR’ with ‘N’ rows and ‘M’ columns in which each element contains only two values,i.e., 0 and 1. Your task is to convert the given matrix into the Good matrix in which if an element is 0, you need to set all elements values present in its entire row and column to 0.

#### For example:

```
Consider ARR = [[1 , 0 , 1] ,
[1 , 1 , 1] ,
[1 , 1 , 1]],
the Good matrix after updating the given matrix as described in the question is
[[0 , 0 , 0] ,
[1 , 0 , 1] ,
[1 , 0 , 1]].
Since ARR[0][1] is 0, we need to set all element’s values present in 0-th row and 1-th column to 0.
```

#### Note :

```
You do not need to print the matrix. Just change in the given input.
```

##### Input format :

```
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two integers, 'N' and ‘M’, denoting the number of rows and columns in the array.
The Next 'N' lines of each test case contain 'M' space-separated integers denoting the elements of the array 'ARR'.
```

##### Output format :

```
For each test case, return the Good matrix after updating the given matrix as described in the question.
Print the output of each test case in a separate line
```

##### Constraints :

```
1 <= T <= 20
1 <= N <= 300
1 <= M <= 300
ARR[i][j] can only contain two values, i.e, 0 and 1.
Where 'T' denotes the number of test cases, 'N' and 'M' denotes the number of rows and the number of columns in the array ‘ARR’ respectively, and 'ARR[i][j]' denotes the ’j-th’ element of 'i-th' row of the array 'ARR'.
Time Limit: 1sec
```

A simple method is to create a 2-dimensional array to store the changes we need to update in the original matrix to convert the given matrix into the Good matrix.

Our approach will be to create a 2-dimensional array **answer** with **N** rows and **M **columns, and we will copy all elements value present in the matrix **ARR** into the matrix **answer**. We will iterate the variable **row** from **0** to **N - 1,** and in each iteration, we will iterate **col** from **0** to **M - 1**.

- We will check if
**ARR[row][col]**is equal to 0, then we need to set all elements value in the entire row and column of**ARR[row][col]**to 0. We will iterate**index**from**0**to**N - 1**, and set**answer[index][col]**as 0. - We will iterate
**index**from**0**to**M - 1**, and set**answer[row][index]**as 0.

In the end, the matrix **answer **is the Good matrix which we will get after updating the given matrix as described in the question. We will return the matrix **answer**.

**Algorithm:**

- Create a 2-dimensional array
**answer**with**N**rows and**M**columns, which we will use to convert the given matrix into the Good matrix. We will update the changes in the matrix**answer**. - Copy all elements value present in the array
**ARR**into the array**answer**. - Iterate
**row**from**0**to**N - 1**.- Iterate
**col**from**0**to**M - 1**.- Check if
**ARR[row][col]**is equal to 0.- Iterate
**index**from**0**to**N - 1**, and set**answer[index][col]**as 0. - Iterate
**index**from**0**to**M - 1**, and set**answer[row][index]**as 0.

- Iterate

- Check if

- Iterate
- Return the matrix
**answer**.

The basic idea is to create an array for all rows and an array for all columns in which we will keep the information of those rows and columns whose value we need to set as 0 for the entire row and column.

We will create array **rows** of size **N** and array **columns** of size **M**. The array **rows** will keep the record of all rows, and the array **columns** will keep the record for all columns whose value of all elements we need to set to 0. Initially, all elements of **rows** and **columns** will contain the value 0. We will set the element’s value to 1 if we need to set all element values present in that particular row or column to 0.

- We will iterate the variable
**index**from**0**to**N - 1,**and in each iteration, we will iterate**pos**from**0**to**M - 1**. We will check if**ARR[index][pos]**is equal to**0**, then we need to set all elements in the row**index**and the column**pos**to 0. We will set**rows[index]**and**columns[pos]**as 1. - Now, we will update the changes in the original matrix. We will iterate the variable
**index**from**0**to**N - 1,**and in each iteration, we will iterate**pos**from**0**to**M - 1**. We will check either**rows[index]**or**columns[pos]**is equal to 1, then we will update**ARR[index][pos]**with the value 1.

In the end, the matrix **ARR** is converted into the Good matrix. We will return the matrix **ARR**.

**Algorithm:**

- Create an array
**rows**of size**N**and**columns**of size**M**. The element of the array**rows,**and the array**columns**will contain the value 1 if we need to set all elements value present in that particular row and column to 0. - Iterate
**index**from**0**to**N - 1**.- Iterate
**pos**from**0**to**M - 1**.- Check if
**ARR[index][pos]**is equal to 0.- Update
**rows[index]**with the value 1. - Update
**columns[pos]**with the value 1.

- Update

- Check if

- Iterate
- Iterate
**index**from**0**to**N-1**.- Iterate
**pos**from**0**to**M - 1**.- Check either
**rows[index]**is equal to 1 or**columns[pos]**is equal to 1.- Set
**ARR[index][pos]**as 0.

- Set

- Check either

- Iterate
- Return the matrix
**ARR**.

As we have discussed in the previous approach, we have created an array for all rows and an array for all columns to keep information of those rows and columns whose value we need to set to 0 for the entire row and column. In this approach, we will keep the record of all rows and columns in the given matrix. We will use the 0’th row and 0’th column of the matrix to keep to record for all rows and columns.

To make this approach work, we will maintain a variable **isCol, **which will store if we need to set all elements value in the 0’th column to 0.

- We will iterate the variable
**row**from**0**to**N - 1**. In each iteration, we will check if**ARR[row][0]**is equal to 0, then we need to set all elements in the 0’th column to 0. So, we will update**isCol**with the value**true**. We will iterate the variable**column**from**0**to**M - 1**. We will check if**ARR[row][colum]**is equal to 0, then we need to set all in the entire row and column of**ARR[row][col]**to 0 and we will update**ARR[0][column]**and**ARR[row][0]**with the value 0. - Now, we will update changes in the given matrix. We will iterate the variable
**row**from**0**to**N - 1**. In each iteration, We will iterate the variable**column**from**0**to**M - 1**. We will check either**ARR[row][0]**or**ARR[0][column]**is equal to 0, then we will update**ARR[row][column]**with the value 0. - Now, we need to take care of the 0’th row and 0’th column. We will check
**ARR[0][0]**is equal to 0, and then we need to set all elements in the 0’th row to 0. We will iterate the variable**column**from**0**to**M - 1**, and we will update**ARR[0][column]**with the value 0. - We will check if
**isCol**is equal to**true**, then we need to set all elements in the 0’th column to 0. We will iterate the variable**row**from**0**to**N - 1**, and we will update**ARR[row][0]**with the value 0.

In the end, the matrix **ARR** is converted into the Good matrix. We will return the matrix **ARR**.

**Algorithm:**

- Set the variable
**isCol**as**false**. The variable**isCol**stores if we need to set all element’s value in the 0’th column to 0. - Iterate
**row**from**0**to**N - 1**.- Check if
**ARR[row][0]**is equal to 0.- Update the variable
**isCol**with**true**.

- Update the variable
- Iterate
**column**from 1 to**M - 1**.- Check if
**ARR[row][column]**is equal to 0.- Update
**ARR[0][column]**with the value 0. - Update
**ARR[row][0]**with the value 0.

- Update

- Check if

- Check if
- Iterate
**row**from**1**to**N - 1**.- Iterate
**column**from**1**to**M - 1**.- Check either
**ARR[row][0]**is equal to 0 or**ARR[0][column]**is equal to 0, then update**ARR[row][column]**with the 0.

- Check either

- Iterate
- Check if
**ARR[0][0]**is equal to 0.- Iterate
**column**from 0 to**M - 1**, update**ARR[0][column]**with the 0.

- Iterate
- Check if
**isCol**is equal to**true**.- Iterate
**row**from 0 to**N - 1**, and update**ARR[row][0]**with the 0.

- Iterate
- Return the matrix
**ARR**.