Coverage of all Zeros in a Binary Matrix

JavaView on GFG

Time: O(n*m)

Space: O(n*m)

Intuition

Find minimum number of flips to cover all zeros. BFS from all ones simultaneously (multi-source BFS).

Algorithm

1Multi-source BFS from all 1-cells. For each 0-cell: distance = BFS steps to reach it.
2Minimum flips = max distance to cover all zeros.

Common Pitfalls

•Standard multi-source BFS. Each 0 is "covered" when a 1 spreads to it. Count layers needed.

Coverage of all Zeros in a Binary Matrix.java

Java

// Approach: BFS/DFS from all 1-cells simultaneously. Track minimum distance to reach each 0-cell.
// Time: O(n*m) Space: O(n*m)
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?