Coverage of all Zeros in a Binary Matrix

Time: O(n*m)

Space: O(1)

Problem Overview

Coverage measures how many 1-cells are immediately next to each 0-cell.

Intuition

Coverage measures how many 1-cells are immediately next to each 0-cell. Scan the grid; for every zero, check the four orthogonal neighbors (left, right, up, down). Each neighbor that equals 1 adds one to the answer. The result is the total number of zero–one adjacencies counted from the zero side.

Algorithm

1Initialise count = 0.
2For each cell (i, j) where matrix[i][j] == 0:
3If j > 0 and matrix[i][j - 1] == 1, increment count.
4If j < m - 1 and matrix[i][j + 1] == 1, increment count.
5If i > 0 and matrix[i - 1][j] == 1, increment count.
6If i < n - 1 and matrix[i + 1][j] == 1, increment count.
7Return count.

Example Walkthrough

Input: matrix = [[0,1],[1,0]]

1. Zero at (0,0): right is 1 → +1; bottom is 1 → +1.
2. Zero at (1,1): left is 1 → +1; top is 1 → +1.
3. Total coverage = 4.

Output: 4

Common Pitfalls

• Check array bounds before each neighbor access.
• Only four directions — diagonals do not count.
• This is adjacency counting, not multi-source BFS distance.

Coverage of all Zeros in a Binary Matrix.java

Java

// Approach: For each 0-cell, count how many of its four orthogonal neighbors are 1.
// Each adjacent 1 contributes one to the total coverage. Sum over all zeros in the matrix.
// Time: O(n*m) Space: O(1)
class Solution {

    public int FindCoverage(int[][] matrix) {
        int cnt = 0;
        int n = matrix.length;
        int m = matrix[0].length;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) {
                    if (j > 0 && matrix[i][j - 1] == 1) {
                        cnt++;
                    }

                    if (i < n - 1 && matrix[i + 1][j] == 1) {
                        cnt++;
                    }

                    if (j < m - 1 && matrix[i][j + 1] == 1) {
                        cnt++;
                    }

                    if (i > 0 && matrix[i - 1][j] == 1) {
                        cnt++;
                    }
                }
            }
        }

        return cnt;
    }
}

Was this solution helpful?