Leetcode 1254. Number of Closed Islands

Problem Explanation

This problem is about finding the number of fully surrounded islands on a grid. An island is considered a group of land cells (0s) connected to each other either horizontally or vertically. A closed island is the one that is completely surrounded by water, meaning all around it (from all four directions: left, right, top and bottom), there are water cells (1s).

We are provided a 2-D matrix containing either 0 (representing land) or 1 (representing water). The goal of the problem is to return the number of closed islands present in the grid.

Let's illustrate this with an example:

Consider the grid: [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]

Here, we have 2 closed islands. The first closed island is the 4-cell island at the top-right part of the grid and the other closed island is the 1-cell island near the center of the grid. Both these islands are completely surrounded by water.

Solution Approach

The solution can be found by using the concept of Depth-First Search (DFS). DFS is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some node as the root node in the graph case) in the case of a tree or at some arbitrary node in the graph case and explores as far as possible along each branch before going back.

The approach to the solution could be thought of in two steps.

1. First, we perform DFS on all the border "lands" to turn them into "waters". This will help us remove islands that are connected to the borders, because those cannot be closed islands.

2. Then, we perform DFS on the rest "lands". If it is a closed island, then the DFS will turn all the lands in this closed island into "waters". So each time we perform DFS, we get a closed island.

Now let's proceed with the solutions in different programming languages.

Python Solution

1
2python
3class Solution:
4    def closedIsland(self, grid: List[List[int]]) -> int:
5        n, m = len(grid), len(grid[0])
6        directions = [(1,0),(-1,0),(0,1),(0,-1))
7        
8        def dfs(i,j):
9            if i < 0 or j < 0 or i >= n or j >= m or grid[i][j] == 1:
10                return
11            grid[i][j] = 1
12            for x,y in directions:
13                dfs(i+x, j+y)
14
15        for i in range(n):
16            for j in range(m):
17                if grid[i][j] == 0 and (i in [0, n-1] or j in [0, m-1]):
18                    dfs(i, j)
19
20        count = 0        
21        for i in range(n):
22            for j in range(m):
23                if grid[i][j] == 0:
24                    dfs(i, j)
25                    count += 1
26        return count 

The grid is scanned twice. The first time we scan the grid, we use the DFS traversal to find and sink the islands which are connected to the border. After that, for the second time we scan the grid, we sink the rest of the islands while incrementing the counter for each island we sink. At the end, we return the counter.

Java Solution

1
2java
3class Solution {
4    public int closedIsland(int[][] grid) {
5        int count = 0;
6        for(int i = 0; i < grid.length; i++) {
7            for(int j = 0; j < grid[0].length; j++) {
8                if(grid[i][j] == 0 && isClosedIsland(grid, i, j)) {
9                    count++;
10                }
11            }
12        }
13        return count;
14    }
15    
16    private boolean isClosedIsland(int[][] grid, int i, int j) {
17        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
18            return false;
19        }
20        if(grid[i][j] == 1) {
21            return true;
22        }
23        grid[i][j] = 1;
24        boolean down = isClosedIsland(grid, i+1, j);
25        boolean up = isClosedIsland(grid, i-1, j);
26        boolean left = isClosedIsland(grid, i, j-1);
27        boolean right = isClosedIsland(grid, i, j+1);
28        return down && up && left && right;
29    }
30}

The isClosedIsland function checks if a land cell (0) is a part of a closed island by performing DFS on it. It returns False in case the land cell is part of an open island or lies at the edge of the grid. It returns True if it is part of a closed island.

JavaScript Solution

1
2javascript
3var closedIsland = function(grid) {
4    let result = 0;
5    
6    function dfs(x, y, value) {
7        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) {
8            return 0;
9        }
10        if (grid[x][y] !== 0) {
11            return 1;
12        }
13        grid[x][y] = value;
14        let top = dfs(x + 1, y, value);
15        let down = dfs(x - 1, y, value);
16        let left = dfs(x, y - 1, value);
17        let right = dfs(x, y + 1, value);
18        
19        return top && down && left && right;;
20    }
21    
22    for (let i = 0; i < grid.length; i++) {
23        for (let j = 0; j < grid[0].length; j++) {
24            if (i === 0 || i === grid.length - 1 || j === 0 || j === grid[0].length - 1) {
25                dfs(i, j, 1);
26            }
27        }
28    }
29    
30    for (let i = 0; i < grid.length; i++) {
31        for (let j = 0; j < grid[0].length; j++) {
32            if (grid[i][j] === 0) {
33                result += dfs(i, j, 1);
34            }
35        }
36    }
37    
38    return result;
39};

In this JavaScript solution, we create a helper function dfs to handle the depth first search process. The function also checks if the cell is out of range, and if it is, it returns 0. We then traverse the edges of the grid and DFS all the "lands". After that we traverse the whole grid and for all "lands" we found, we increment the result and DFS them.

C++ Solution

1
2cpp
3class Solution {
4public:
5    int closedIsland(vector<vector<int>>& grid) {
6        if(grid.empty()) return 0;
7        int count = 0;
8        for(int i=0; i<grid.size(); i++)
9        {
10            for(int j=0; j<grid[0].size(); j++)
11            {
12                if(grid[i][j] == 0)
13                {
14                    if( dfs(i, j, grid) )
15                        count++;
16                }
17            }
18        }
19        return count;
20        
21    }
22    bool dfs(int x, int y, vector<vector<int>>& grid)
23    {
24        if(x<0 || y<0 || x>=grid.size() || y>=grid[0].size())
25            return false;
26        
27        if(grid[x][y] == 1)
28            return true;
29        
30        //Marking as visited
31        grid[x][y] = 1;
32        
33        bool down = dfs(x+1, y, grid);
34        bool up = dfs(x-1, y, grid);
35        bool left = dfs(x, y-1, grid);
36        bool right = dfs(x, y+1, grid);
37        
38        return down && up && left && right;
39    }
40};

Similar to Java solution, we traverse the grid using nested loops. If the current cell is a land cell (0), we perform DFS on it. If it is a part of closed island, we increment the count.

C# Solution

1
2csharp
3public class Solution {
4    private int _count;
5    private int[][] _directions = new int[][] {
6        new int[] {-1, 0}, // up
7        new int[] {1, 0},  // down
8        new int[] {0, -1}, // left
9        new int[] {0, 1}   // right
10    };
11    public int ClosedIsland(int[][] grid) {
12        if (grid.Length == 0) return 0;
13        for(int i = 0; i < grid.Length; i++) {
14            for(int j = 0; j < grid[i].Length; j++) {
15                if (grid[i][j] == 0) {
16                    _count += DFS(grid, i, j) ? 1 : 0;
17                }
18            }
19        }
20        return _count;
21    }
22    
23    private bool DFS(int[][] grid, int row, int col) {
24        if(row < 0 || col < 0 || row >= grid.Length || col >= grid[0].Length) 
25            return false;
26        if(grid[row][col] == 1)
27            return true;
28        grid[row][col] = 1; // visited
29        bool res = true;
30        foreach(int[] direction in _directions) {
31            res = DFS(grid, row + direction[0], col + direction[1]) && res;
32        }
33        return res;
34    }
35}

The grid is traversed and each land cell is depth-first searched. If the cell is part of a closed island, DFS will return true and the counter is incremented.The ClosedIsland function iterates over the entire grid. If a land cell is found, it increments the count if the DFS method returns true. DFS method recursively checks each of the directions (up, down, left, and right) using the directions array. If the cell is out of the boundaries of the grid, it returns false indicating that the island is not closed.

Conclusively, these solutions demonstrate how DFS can be effectively used to solve problems involving traversal of grids or matrices. Vital concepts such as marking visited nodes and traversing in specified directions can be adapted for other complex problems as well. Therefore, it also opens an avenue for solving similar problems in the realm of data structures and algorithms.

Importantly, it would be worthwhile to consider time and space complexities of these solutions as they use recursive DFS that could cause stack overflow for larger grids. Optimization techniques could potentially be used to mitigate these issues. It is also noteworthy to understand that this specific problem of finding islands, and even more broadly the DFS traversal algorithm, can have other practical applications in areas such as networking, route mapping, web crawlers etc.

Remember, practice is key in mastering these concepts and applying them effectively to problem solving. Happy algorithm designing!