Algorithms to Count the Largest Elements in Their Row and Column in a Matrix

You are given a two-dimensional list of integers matrix containing 1s and 0s. Return the number of elements in matrix such that:

matrix[r][c] = 1
matrix[r][j] = 0 for every j ≠ c and matrix[i][c] = 0 for every i ≠ r
Constraints

0 ≤ n, m ≤ 250 where n and m are the number of rows and columns in matrix
Example 1
Input

1 2 3 4 5

matrix = [     [0, 0, 1],     [1, 0, 0],     [0, 1, 0] ]

matrix = [
    [0, 0, 1],
    [1, 0, 0],
    [0, 1, 0]
]

Output
3
Explanation
We have matrix[0][2], matrix[1][0] and matrix[2][1] meet the criteria.

Example 2
Input

1 2 3 4 5

matrix = [     [0, 0, 1],     [1, 0, 0],     [1, 0, 0] ]

matrix = [
    [0, 0, 1],
    [1, 0, 0],
    [1, 0, 0]
]

Output
1
Explanation
Only matrix[0][2] meet the criteria. The other two 1s share the same column.

Largest Elements in Their Row and Column in a Matrix

One we have a 1 in the matrix, we increment the corresponding counters for rows and cols. Thus, the second pass we can check if the counter is one (which means current element is the largest in the its row and column).

The time complexity is O(RC) and the space complexity is also O(RC).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def largestNumberInMatrix(self, matrix):
        ans = 0
        row = len(matrix)
        col = len(matrix[0])
        rows = [0 for _ in range(row)]
        cols = [0 for _ in range(col)]
        for r in range(row):
            for c in range(col):
                if matrix[r][c] == 1:
                    rows[r] += 1
                    cols[c] += 1
        for r in range(row):
            for c in range(col):
                if matrix[r][c] == 0:
                    continue
                if rows[r] == 1 and cols[c] == 1:
                    ans += 1
        return ans

class Solution:
    def largestNumberInMatrix(self, matrix):
        ans = 0
        row = len(matrix)
        col = len(matrix[0])
        rows = [0 for _ in range(row)]
        cols = [0 for _ in range(col)]
        for r in range(row):
            for c in range(col):
                if matrix[r][c] == 1:
                    rows[r] += 1
                    cols[c] += 1
        for r in range(row):
            for c in range(col):
                if matrix[r][c] == 0:
                    continue
                if rows[r] == 1 and cols[c] == 1:
                    ans += 1
        return ans

–EOF (The Ultimate Computing & Technology Blog)