Day 2 : Find K-th Row

Easy

0/40

Average time to solve is 15m

Contributed by

35 upvotes

Asked in companies

Problem statement

Given a square binary matrix ‘mat[n][n]’, find ‘K’ such that all elements in the Kth row are ‘0’ and all elements in the Kth column are ‘1’. The value of mat[k][k] can be anything (either ‘0’ or ‘1’). If no such k exists, return ‘-1’.

For example

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.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

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.

Output Format :

 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.

Note:

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

Constraints:

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

Sample Input 1 :

Sample Output 1 :

Explanation For Sample Output 1:

For the first test case, column 1 contains all ones. Also except mat[1][1] all numbers in row 1 are 0.

Sample Input 2:

Sample Output 2:

-1
0

Hint 1

Hint 2

Try for every value of K.

Approaches (2)

Approach 1

Approach 2

Brute Force

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.

Time Complexity

O(N^2) Where N is the size of the input matrix.

For every row, we spend O(N) time checking for row and O(N) to check for the column. Hence a total of O(N*N) time in total.

Space Complexity

O(1)

Since only constant space is used to check for every row and column.

(100% EXP penalty)

Day 2 : Find K-th Row

Console