Given a binary matrix having n rows and m columns, your task is to find the sum of coverage of all zeros in the matrix where coverage for a particular 0 is defined as a total number of ones around a zero in left, right, up, and bottom directions.
Examples:
Input:
matrix = [[0, 1, 0], [0, 1, 1],
[0, 0, 0]] Output: 6
Input:
matrix = [[0, 1]] Output: 1
Expected Time Complexity: O(n * m)
Expected Space Complexity: O(1)
Constraints:
1 <= mat.size, mat[0].size <= 100
Approach 01:
-
C++
-
Python
class Solution {
public:
int FindCoverage(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
int total_coverage = 0;
vector<pair<int, int>> directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (matrix[i][j] == 0) {
int coverage = 0;
for (auto direction : directions) {
int dx = direction.first;
int dy = direction.second;
int new_x = i + dx;
int new_y = j + dy;
if (new_x >= 0 && new_x < rows && new_y >= 0 && new_y < cols && matrix[new_x][new_y] == 1) {
coverage++;
}
}
total_coverage += coverage;
}
}
}
return total_coverage;
}
};
from typing import List
class Solution:
def FindCoverage(self, matrix: List[List[int]]) -> int:
rows = len(matrix)
cols = len(matrix[0])
total_coverage = 0
directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
for i in range(rows):
for j in range(cols):
if matrix[i][j] == 0:
coverage = 0
for direction in directions:
dx, dy = direction
new_x = i + dx
new_y = j + dy
if 0 <= new_x < rows and 0 <= new_y < cols and matrix[new_x][new_y] == 1:
coverage += 1
total_coverage += coverage
return total_coverage