Problem Statement in English

You’re given an m x n binary matrix mat. A position (i, j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0.

Your task is to return the number of special positions in mat.

Approach

We can simply store the count of 1s in each row and column in two hashmaps.

Then we can traverse the matrix again and check for each position if it’s a special position or not.

And we’re done!

Solution in Python


class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        rowHM = defaultdict(int)
        colHM = defaultdict(int)

        M = len(mat)
        N = len(mat[0])
        
        res = 0

        for i in range(M):
            for j in range(N):
                if mat[i][j] == 1:
                    rowHM[i] += 1
                    colHM[j] += 1
        
        for i in range(M):
            for j in range(N):
                if mat[i][j] == 1 and rowHM[i] == 1 and colHM[j] == 1:
                    res += 1

        return res

Complexity

  • Time: $O(M \times N)$
    Since we need to traverse the entire matrix twice, once to calculate the count of 1s in each row and column and once to check for special positions.

  • Space: $O(M + N)$
    Since we store the count of 1s in each row and column.

And we are done.