Special Positions in a Binary Matrix

Difficulty: Easy | Acceptance: 72.70% | Paid: No Topics: Array, Matrix

Given an m x n binary matrix mat, return the number of special positions in 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 (in other words, mat[i][j] is the only element that is 1 in its row and column).

• Examples
• Constraints
• Brute Force
• Precompute Sums

Examples

Input: mat = [[1,0,0],[0,0,1],[1,0,0]]
Output: 1
Explanation: (1, 2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.

Input: mat = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Explanation: (0, 0), (1, 1), (2, 2) are special positions.

Constraints

m == mat.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j] is either 0 or 1.

Brute Force

Intuition For each cell containing 1, verify that all other elements in its row and column are 0 by scanning through them.

Steps

• Iterate through each cell in the matrix
• When finding a 1, scan the entire row to check if it’s the only 1
• If valid, scan the entire column to check if it’s the only 1
• Increment count if both checks pass

from typing import List

class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        count = 0
        
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    valid = True
                    for k in range(n):
                        if k != j and mat[i][k] != 0:
                            valid = False
                            break
                    if not valid:
                        continue
                    for k in range(m):
                        if k != i and mat[k][j] != 0:
                            valid = False
                            break
                    if valid:
                        count += 1
        return count

Complexity

• Time: O(m × n × (m + n))
• Space: O(1)
• Notes: Simple but inefficient for larger matrices due to repeated scanning

Precompute Sums

Intuition Precompute the sum of each row and column once, then a position is special if its value is 1 and both its row sum and column sum equal 1.

Steps

• Compute sum of all elements in each row
• Compute sum of all elements in each column
• Iterate through matrix and count positions where value is 1, row sum is 1, and column sum is 1

from typing import List

class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        row_sum = [sum(row) for row in mat]
        col_sum = [sum(mat[i][j] for i in range(m)) for j in range(n)]
        
        count = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1 and row_sum[i] == 1 and col_sum[j] == 1:
                    count += 1
        return count

Complexity

• Time: O(m × n)
• Space: O(m + n)
• Notes: Optimal solution with linear time complexity, trading space for efficiency