Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A one is special exactly when it is the only one in both its row and its column. Counting those totals once avoids rescanning an entire row and column for every candidate cell.

Approach

Make a first matrix pass to count ones per row and per column. In a second pass, count cells whose value is one and whose two totals are both one. Return that count. Requiring the cell itself to be one is essential: a zero at the intersection of a one-count row and column is not a special position.

class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        rows = defaultdict(int)
        cols = defaultdict(int)

        for i in range(n):
            for j in range(m):
                if mat[i][j] == 1:
                    rows[i] += 1
                    cols[j] += 1

        res = 0

        for i in range(n):
            for j in range(m):
                if mat[i][j] == 1 and rows[i] == 1 and cols[j] == 1:
                    res += 1

        return res

Complexity analysis

For an R × C matrix, two full scans take O(RC) time. Row and column count maps use O(R + C) auxiliary space.