New update is available. Click here to update.

Last Updated: 4 Dec, 2020

Difficulty: Easy

```
Consider the following matrix :
0 1 1
0 1 0
1 1 0
You can see that row 1 (0-based) contains all 0’s except mat[1][1] and column 1 contains all 1’s. Hence the answer for the above case is 1.
```

```
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains an integer N representing the number in the problem statement.
Then N lines follow, each of which contains N space-separated integers denoting the elements of the matrix.
```

```
For each test case print an integer denoting the value of K if such K exists else print -1.
Output for each test case will be printed in a separate line.
```

```
You are not required to print anything; it has already been taken care of. Just implement the function.
```

```
1 <= T <= 5
1 <= N <= 1000
0 <= Aij <= 1
Time Limit: 1sec
```

**Approach:**

For each row, we assume this to be the answer. For each number except mat[k][k] we check if it is 1 and for every number in the kth column we check if it is 1. If both the conditions match, we return this row. If no rows match we return -1.

**Algorithm:**

- Start K from 0 to n - 1.
- Check if all numbers in kth row except mat[k][k] are 0.
- Check if all numbers in kth column except mat[k][k] are 1.
- If the current K satisfies the above conditions return it.
- Return -1 if no such k is found.

There can be at most one ‘K’ that can be qualified to be an answer. If we traverse the given matrix from a corner (preferably from top right and bottom left), we can quickly discard the complete row or complete column based on the below rules.

a) If mat[i][j] is 0 and i != j, then column j cannot be the solution.

b) If mat[i][j] is 1 and i != j, then row i cannot be the solution.

**Algorithm:**

- Start from top right corner, i.e., i = 0, j = n-1. Initialize result as -1.
- Do the following until we find the result or reach outside the matrix.
- If mat[i][j] is 0, then check all elements on left of j in current row.
- If all elements on the left of j are also 0, then set the result as i.
- If all left side elements of i'th row are not 0, then this row cannot be a solution, increment i.

- If mat[i][j] is 0, then check all elements on left of j in current row.
- If mat[i][j] is 1, then check all elements below i in current column.
- If all elements below i are 1, then set the result as j.
- If all elements of j'th column are not 1, then this column cannot be a solution decrement j.

- If the result is -1, return it.
- Else check the validity of the result by checking all row and column elements of the result.

Popular Interview Problems: