1s Surrounded by 0s

Intuition

A cell with value 1 is not surrounded if it can reach the border through adjacent 1s. So instead of trying to prove each 1 is enclosed, mark all border-connected 1s first. Whatever 1s remain unmarked are exactly the ones surrounded by 0s.

Algorithm

1Create a visited matrix of the same size as the grid.
2Traverse the first and last column; whenever a border cell contains 1 and is not visited, run DFS from it.
3Traverse the first and last row and do the same DFS marking for border 1s.
4After all border-connected regions are marked, scan the full grid.
5Count every cell where grid[i][j] == 1 and visited[i][j] == false.
6Return that count.

Example Walkthrough

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

1.Border 1s are at (3,0) and (3,3). DFS from them marks only those cells because they are isolated.
2.The 1s at (1,1), (1,2), and (2,1) are never reached from the border.
3.These three cells are enclosed by 0s on every side through their connected component.

Output: 3

Common Pitfalls

•Do not count border-connected 1s just because the border cell itself is 0; the whole connected component matters.
•A visited matrix is necessary unless you mutate the grid in place during DFS.
•Remember to scan both rows and columns on the border; missing one side will overcount surrounded cells.

1s Surrounded by 0s.java

Java


// Approach: Run DFS from every border cell containing 1 and mark all border-connected 1s as visited.
// Any 1 not reached by this border flood-fill is fully surrounded by 0s, so count those cells.
// Time: O(n * m) Space: O(n * m)

class Solution {

    int cntOnes(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            if (grid[i][0] == 1 && !visited[i][0]) {
                dfs(grid, visited, i, 0);
            }
            if (grid[i][m - 1] == 1 && !visited[i][m - 1]) {
                dfs(grid, visited, i, m - 1);
            }
        }
        for (int j = 0; j < m; j++) {
            if (grid[0][j] == 1 && !visited[0][j]) {
                dfs(grid, visited, 0, j);
            }
            if (grid[n - 1][j] == 1 && !visited[n - 1][j]) {
                dfs(grid, visited, n - 1, j);
            }
        }

        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    count++;
                }
            }
        }
        return count;
    }

    void dfs(int[][] grid, boolean[][] visited, int x, int y) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0 || visited[x][y]) {
            return;
        }
        visited[x][y] = true;
        dfs(grid, visited, x + 1, y);
        dfs(grid, visited, x - 1, y);
        dfs(grid, visited, x, y + 1);
        dfs(grid, visited, x, y - 1);
    }
};

Was this solution helpful?