Special Positions in a Binary Matrix — Problem & Solution
Special Positions in a Binary Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Special Positions in a Binary Matrix is an easy coding problem on arrays and matrix, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays, Matrix
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an m × n binary matrix mat, return the number of special positions.
A position (i, j) is special if mat[i][j] == 1 and every other element in row i and column j is 0.
Example 1
Input: mat = [[1,0,0],[0,0,1],[1,0,0]]
Output: 1
Explanation: Only (1,2) is alone in both its row and its column.
Example 2
Input: mat = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Example 3
Input: mat = [[0,0],[0,0]]
Output: 0
Constraints
1 <= mat.length, mat[i].length <= 8mat[i][j] is 0 or 1.
Hints for Special Positions in a Binary Matrix
Hint 1
Precompute the sum of every row and every column in one pass.
Hint 2
A cell is special exactly when it holds a 1 and both of those sums equal 1.
How to solve Special Positions in a Binary Matrix
Precompute row and column sums; a cell is special iff it holds a 1 and both its row sum and column sum equal 1.
Approach
- Compute
rowSumandcolSum. - Count cells with
mat[r][c] == 1,rowSum[r] == 1,colSum[c] == 1.
Why it works
"Every other element in the row and column is 0" is equivalent to the sums being exactly 1 when the cell itself is 1.
Complexity
- Time —
O(m · n) - Space —
O(m + n)
Pitfalls
- Rechecking the row and column per cell is
O(m·n·(m+n))— precompute instead.
Reference solution
Python
def numSpecial(mat) -> int:
m, n = len(mat), len(mat[0])
row_sum = [sum(row) for row in mat]
col_sum = [sum(mat[r][c] for r in range(m)) for c in range(n)]
return sum(1 for r in range(m) for c in range(n)
if mat[r][c] == 1 and row_sum[r] == 1 and col_sum[c] == 1)Java
public static int numSpecial(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[] rowSum = new int[m];
int[] colSum = new int[n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
rowSum[r] += mat[r][c];
colSum[c] += mat[r][c];
}
}
int count = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (mat[r][c] == 1 && rowSum[r] == 1 && colSum[c] == 1) count++;
}
}
return count;
}C++
int numSpecial(vector<vector<int>>& mat) {
int m = (int) mat.size(), n = (int) mat[0].size();
vector<int> rowSum(m, 0), colSum(n, 0);
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
rowSum[r] += mat[r][c];
colSum[c] += mat[r][c];
}
}
int count = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (mat[r][c] == 1 && rowSum[r] == 1 && colSum[c] == 1) count++;
}
}
return count;
}JavaScript
var numSpecial = function(mat) {
const m = mat.length, n = mat[0].length;
const rowSum = new Array(m).fill(0);
const colSum = new Array(n).fill(0);
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
rowSum[r] += mat[r][c];
colSum[c] += mat[r][c];
}
}
let count = 0;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (mat[r][c] === 1 && rowSum[r] === 1 && colSum[c] === 1) count++;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal