1254. Number Of Closed Islands

/**

 * 1254. Number of Closed Islands

 * Given a 2D grid consists of 0s (land) and 1s (water).  An island is a maximal 4-directionally connected group of

 * 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

 * Return the number of closed islands.

*/

See solution on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/NumberOfClosedIslands.java

Number of Islands is a frequent interview question. But this question poses a tricky twist. Its asking for number of closed islands, where closed occurs when an island is surrounded by water on all sides.

The approach taken below is to start from the edges and traverse the land via dfs while invalidating the connected land.

Based on this logic, the land areas left are simply those that are surrounded by water since the dfs from edges wasn’t able to invalidate those land areas.

Then its simply a matter of traversing land areas via dfs, and each time a new land area is found, we increment the closed island count while invalidating the connected land cells.

Here is the code:

public int closedIsland(int[][] grid) {
    int islands = 0;
    cols = grid[0].length;
    rows = grid.length;
    this.grid = grid;
    //invalidate cells from top and bottom rows that have a land
    for (int i = 0; i < cols; i++) {
        dfs(0, i);
        dfs(rows-1, i);
    }
    //invalidate cells from left and right cols that have a land
    for (int i = 0; i < rows; i++) {
        dfs(i, 0);
        dfs(i, cols-1);
    }
    //check inner cells
    for (int i = 1; i < grid.length; i++) {
        for (int j = 1; j < cols; j++) {
            if (grid[i][j] ==0) {
                dfs(i, j);
                islands++;
            }
        }
    }
    return islands;
}
void dfs(int row, int col) {
    if ( (row < 0) || (row >= rows) || (col < 0) || (col >= cols) || grid[row][col] !=0) {
        return;
    }
    grid[row][col] = -1; //mark as visited
    dfs(row+1, col); //down
    dfs(row-1, col); //up
    dfs(row, col+1); //right
    dfs(row, col-1); //left
}