Special Positions in a Binary Matrix
Easy · Matrix · Array · Matrix
Problem
You are given an m x n binary matrix mat. A position (i, j) is special when mat[i][j] == 1 and every other cell in row i and every other cell in column j is 0.
Return the number of special positions in mat.
Examples
Input: mat = [[0,0,1],[1,0,0],[0,0,1]] Output: 1
Only (1,0) is special: the two 1s in column 2 share a column.
Input: mat = [[1,0],[0,1]] Output: 2
Both 1s are alone in their row and their column.
Input: mat = [[1,1,0],[0,0,0],[0,0,1]] Output: 1
The 1s in row 0 share a row; the 1 at (2,2) is alone, so the answer is 1.
Constraints
- m == len(mat), n == len(mat[i])
- 1 <= m, n <= 100
- mat[i][j] is 0 or 1
Approaches
- Scan the row and column of every 1 — time O(m·n·(m + n)), space O(1)
Follow-up
Only two numbers per line matter: the count of ones. The same precompute-then-check idea answers "how many 1s have exactly k ones in their row and column", and works on pictures written as strings; both are use cases below.
Related problems
Start free on Cariara · Coding problems · System design studio
