Problem

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 an index 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 either 0 or 1. If no such k exists, return -1.

Examples

Example 1:

Input:
mat = [
 [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
Explanation: The 1st row has all 0s and the 1st column has all 1s. mat[1][1] is 0, and it can be 0 or 1.

Example 2:

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

Solution

Method 1 - Naive

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 (n - 1). This is a O(n^2) solution however. How can we do it in O(n)?

A naive approach is to find all rows with a sum at most 1 and then check the corresponding columns to ensure they have a sum of at least (n - 1 ) (where n is number of rows) . However, this approach requires O(n^2) time. How can we achieve this in O(n)?

Method 2 - Two Pointer Technique

If we look at examples closely, 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.

Given this unique k, the candidate row and column intersect at [k, k], where the value can be either 0 or 1, with all other row elements being 0 and all other column elements being 1. How do we find this intersecting point?

We can start from a corner, such as the top-left:

  • If the corner contains a 0, check if the entire row can be a candidate by verifying if all remaining values in the row are 0. If so, validate the column condition. If any value in the row is 1, move to the next row.
  • If the corner contains a 1, verify the column. If all other column values are 1, it is a candidate column; validate the row condition. If any value in the column is 0, move to the next column.

Each step increments either a row or a column, ensuring at most 2n elements are visited, resulting in an O(n) time complexity.

So, here is the approach:

  1. Two Pointers Technique:

    • Initialize two pointers, row and col, at the beginning of the matrix.

  2. Pointer Movement:

    • Move the row pointer down to find a row with all zeros.
    • Move the col pointer across to find a column with all ones.
    • Alternate the pointers based on the satisfaction of the conditions.

  3. Validation:

    • Once a candidate k is identified, validate by checking the entire kth row and kth column to ensure they meet the conditions.

  4. Return Result:

    • Return the index k if valid, otherwise return -1.

Code

Java
public class Solution {
    public int findSpecialIndex(int[][] mat) {
        int n = mat.length;
        int row = 0, col = 0;

        while (row < n && col < n) {
            if (mat[row][col] == 0) {
                if (isRowZero(mat, row, n)) {
                    if (isColOne(mat, col, n)) {
                        return row;
                    } else {
                        col++;
                    }
                } else {
                    row++;
                }
            } else { // mat[row][col] == 1
                if (isColOne(mat, col, n)) {
                    if (isRowZero(mat, row, n)) {
                        return col;
                    } else {
                        row++;
                    }
                } else {
                    col++;
                }
            }
        }

        return -1;
    }

    private boolean isRowZero(int[][] mat, int row, int n) {
        for (int j = 0; j < n; j++) {
            if (mat[row][j] != 0) {
                return false;
            }
        }
        return true;
    }

    private boolean isColOne(int[][] mat, int col, int n) {
        for (int i = 0; i < n; i++) {
            if (mat[i][col] != 1) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] mat = {
            {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}
        };
        System.out.println("Index k: " + sol.findSpecialIndex(mat));  // Expected output: 1
    }
}
Python
class Solution:
    def findSpecialIndex(self, mat: List[List[int]]) -> int:
        n = len(mat)
        row, col = 0, 0

        while row < n and col < n:
            if mat[row][col] == 0:
                if self.is_row_zero(mat, row, n):
                    if self.is_col_one(mat, col, n):
                        return row
                    else:
                        col += 1
                else:
                    row += 1
            else: # mat[row][col] == 1
                if self.is_col_one(mat, col, n):
                    if self.is_row_zero(mat, row, n):
                        return row
                    else:
                        row += 1
                else:
                    col += 1

        return -1

    def is_row_zero(self, mat: List[List[int]], row: int, n: int) -> bool:
        return all(mat[row][j] == 0 for j in range(n))

    def is_col_one(self, mat: List[List[int]], col: int, n: int) -> bool:
        return all(mat[i][col] == 1 for i in range(n))

# Example usage
sol = Solution()
mat = [
    [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]
]
print("Index k:", sol.findSpecialIndex(mat))  # Expected output: 1

Complexity

  • ⏰ Time complexity: O(n), where n is the dimension of the matrix, because we process each row and column index a constant number of times.
  • 🧺 Space complexity: O(1) as only a small, fixed amount of extra space is required.