Find k such that kth row is all zero and kth col is all one in a matrix

Given a Boolean Matrix, find k such that all elements in k’th row are 0 and k’th column are 1. Do it in O(n) time

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

Examples:

Input: mat[n][n] = {{0, 1, 1, 0, 1},
{0, 0, 0, 0, 0},
{1, 1, 1, 0, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1}};
Output: 1
All elements in 1’st row are 0 and all elements in
1’st column are 1. mat[1][1] is 0 (can be any value)

Input: mat[n][n] = {{0, 1, 1, 0, 1},
{0, 0, 0, 0, 0},
{1, 1, 1, 0, 0},
{1, 0, 1, 1, 0},
{1, 1, 1, 1, 1}};
Output: -1
There is no k such that k’th row elements are 0 and
k’th column elements are 1.

A trivial solution would be to find all rows that has sum at most 1 and then check corresponding columns to check if column has sum at least 4 (why?). This is a O(n^2) solution however. How can we do it in O(n)?

Carefully looking into the examples we can see there can be at most one solution of this problem because if we have more than one solution then we have more than one row that satisfies the constraint which automatically tells us that more than one columns in the row has 1, which in turn contradicts the row condition. So, we there is at most one such k.

Now, as there is at most one such k then the candidate row, column is crossing at (k,k) where the value can be either 0 or 1 and all other values in the row are 0 , and all other values in the column are 1. How to find such a intersecting point?

We can actually start from a corner, let’s say the top-left. If this corner contains a 0 then we try to validate if this row can be a candidate. If all other values int the row are zero then it is a candidate row and we need to check for column condition. Otherwise, if there is a one value in the row then this row can’t be the solution and we go to next row.

On the other hand if the corner was a 1 then we have to check the validity of the column. If all other column values are 1 then this is a candidate column and we need to validate the row constraint. Otherwise, if there was a zero in the column then this column can’t be the candidate and we go to next column.

Each time, we are either incrementing a row or a column. So, will visit at most visit 2n numbers of element in this way and hence the time complexity is O(n). Below is the implementation of this idea.

public static int findKthRowCol(int mat[][]){
	int n = mat.length;
	int m = mat[0].length;
	int i = 0;
	int j = 0;
	
	int candidate = -1;
	while(i < n && j < m){
		//check the row for all zero
		if(mat[i][j] == 0){
			int k = j+1;
			while(k < m && mat[i][k] == 0){
				k++;
			}
			
			if(k == m){
				candidate = i;
				break;
			}
			//if not all zero in this row, then this row can't be the candidate
			else{
				i++;
			}
		}
		//check the column for all ones
		else{
			int k = i+1;
			while(k < n && mat[k][j] == 0){
				k++;
			}
			
			if(k == n){
				candidate = i;
				break;
			}
			//if not all are 1 then this col can't be the candidate
			else{
				j++;
			}
		}
	}
	
	//we found a row/cold candidate, validate the rowand columnd
	if(candidate != -1){
		for(j = 0; j<n; j++){
			if(j != candidate && mat[candidate][j] != 0){
				return -1;
			}
		}
		
		for(i = 0; i<n; i++){
			if(i != candidate && mat[i][candidate] != 1){
				return -1;
			}
		}
		
		return candidate;
	}
	
	return candidate;
}