Problem Overview
You are given a binary matrix containing only 0s and 1s.
For every cell containing 0, its coverage is calculated by checking the four directions:
For each direction:
The task is to find the sum of coverage values of all zero cells.
Example 1
Input
1 1 1 0
1 0 0 1
Coverage Calculation
Zero at (0,3)
1 1 1 0
Left → contains 1 → +1
Right → boundary → +0
Up → boundary → +0
Down → contains 1 → +1
Coverage = 2
Zero at (1,1)
Left → contains 1 → +1
Right → contains 1 → +1
Up → contains 1 → +1
Down → boundary → +0
Coverage = 3
Zero at (1,2)
Coverage = 3
Output
2 + 3 + 3 = 8
Example 2
Input
0 1 0
0 1 1
0 0 0
Coverage
| Cell | Coverage |
|---|
| (0,0) | 1 |
| (0,2) | 2 |
| (1,0) | 1 |
| (2,0) | 0 |
| (2,1) | 1 |
| (2,2) | 1 |
Total:
1 + 2 + 1 + 0 + 1 + 1 = 6
Efficient Approach
For every zero cell:
Scan left until boundary.
Scan right until boundary.
Scan upward until boundary.
Scan downward until boundary.
If any direction contains at least one 1, add 1 to coverage.
Finally, return the total coverage.
Since matrix dimensions are at most 100 × 100, this straightforward solution works comfortably.
Java Solution
class Solution {
public int findCoverage(int[][] mat) {
int n = mat.length;
int m = mat[0].length;
int totalCoverage = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i][j] == 0) {
int coverage = 0;
// Left
for (int c = j - 1; c >= 0; c--) {
if (mat[i][c] == 1) {
coverage++;
break;
}
}
// Right
for (int c = j + 1; c < m; c++) {
if (mat[i][c] == 1) {
coverage++;
break;
}
}
// Up
for (int r = i - 1; r >= 0; r--) {
if (mat[r][j] == 1) {
coverage++;
break;
}
}
// Down
for (int r = i + 1; r < n; r++) {
if (mat[r][j] == 1) {
coverage++;
break;
}
}
totalCoverage += coverage;
}
}
}
return totalCoverage;
}
}
Complexity Analysis
Let:
n = number of rows
m = number of columns
Time Complexity
For every cell, we may scan its row and column.
O(n * m * (n + m))
With n, m ≤ 100, this is acceptable.
Space Complexity
O(1)
No extra data structures are used.