island problems

Island problems (Graph)

In the previous post, we discussed Graph Colouring and we will continue with some Island Problems related to Graph.

In this post, we will solve some island problems from leet code which are asked in interviews frequently. So, let’s start.

Leetcode 200 : Number of Islands

Given a 2D grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:
Input: grid = [ 
   ["1","1","1","1","0"],
   ["1","1","0","1","0"],
   ["1","1","0","0","0"], 
   ["0","0","0","0","0"] 
] 
Output: 1

Example 2:
Input: grid = [
   ["1","1","0","0","0"], 
   ["1","1","0","0","0"], 
   ["0","0","1","0","0"], 
   ["0","0","0","1","1"] 
] 
Output: 3

Analysis of Problem Statement

The problem statement says that we are given a 2-D binary matrix where 1’s represent land and 0’s represent water and we have to find a number of islands.

By the number of islands, we mean we have to find a number of connected lands. Let’s understand it by an example.

Island Problems

In the above example, there are a total of three islands present. NOTE that diagonals are not considered here.

The islands are formed by connecting adjacent land vertically and horizontally, not diagonally.

I Hope, problem statement is clear to you now think of a solution which will solve this problem.

Approach to the problem

If you observe the problem clearly, we basically have to find a number of connected components in the matrix. We have discussed connected components in this post.

As we have discussed earlier that for counting the number of connected components, we use DFS traversal. So here also we will use it.

An island can only be connected to four neighbors as mentioned in the problem.

So, unlike standard DFS Traversal where we call df() for all adjacent vertices, here we will call DFS() for all four neighbors (Left, Right, top, down).

Let’s see the code for it,

class Solution {
public:
    
    void dfs(vector<vector<char>> &grid, int i, int j)
    {
        if(i < 0 || i>=grid.size() || j < 0 || j >= grid[i].size()) return;
        if(grid[i][j] == '0') return;
        
        grid[i][j] = '0';
        
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
    }
    
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0)
            return 0;
        
        int numsIslands = 0;
        for(int i = 0;i < grid.size(); i++)
        {
            for(int j = 0; j < grid[i].size(); j++)
            {
                if(grid[i][j] == '1'){
                    dfs(grid,i,j);
                    numsIslands++;
                }
            }
        }
        return numsIslands;
    }
};

In the above code, we simply did DFS Traversal where we call dfs() whenever grid[i][j] = ‘1’.

After that, we define a base condition, where we mentioned the boundary condition and then we call dfs() in all four directions.

This dfs() call will run for one component of the island and as soon as it finds the island, it will return back to the main function, and again it will try to find another island and this process will continue.

Hope code and explanation are clear to you. NOTE we have also converted visited grid[i][j] to ‘0’ so that we cannot visit the same index again.

Now let’s move ahead, the above problem was a simply DFS traversal problem where we simply have to find number of islands but there are many variations for above problem and of that we are going to discuss one more variation of it.

Leetcode 1254 : Number of closed Islands

Given a 2D grid consists of 0's (land) and 1's(water).  An island is a maximal 4-directionally connected group of 0's and a closed island is an island totally (all left, top, right, bottom) surrounded by 1's.

Return the number of closed islands.

Example 1:

Input: 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]
]
Output: 2

Explanation:
Islands in gray are closed because they are completely surrounded by water (group of 1's).
Island Problems
Example 2:

Input: grid = [
[0,0,1,0,0],
[0,1,0,1,0],
[0,1,1,1,0]
]
Output: 1
Island Problems
Example 3:

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

Output: 2

Analysis of Problem Statement

This problem is similar to the problem which we have discussed earlier. Here the only variation is that we have to count the number of closed Islands instead of the only the number of islands. (Island Problems)

A closed island basically means
it will be surrounded by water in all four directions.

The problem statement has been explained pretty well and I don’t think it requires any further explanation.

NOTE here 0’s represent land and 1’s represent water.

It is highly recommended to try this problem before moving ahead.

Approach to the Island problem

It’s pretty clear that counting the number of closed islands directly will be painful.

Instead what we will do is, we will first remove the islands which are not closed, and then we will simply count the number of islands as discussed before.

How we will find which island is closed which are not..?

The reason is simple, the island will be called ‘closed-island’ only when all four neighboring regions will be surrounded by water. In other words, none of the lands of the island are near to boundary edges.

Let’s understand it by an example,

Island Problems

In the above, for example, both are islands that are not closed islands because there are lands of the island that are near to boundary edges.

Let’s see another example,

Island Problems

In this example, one island is present where none of the land’s of the island is near to boundary edges.

Hope, you understood the logic behind ‘closed-island’.

So, what we will do is we will remove all the island which are near to boundary edges and we can do this by checking if any boundary grid[i][j] equals 0 if present we will remove the whole island connected to that grid.

Please don’t confuse it with the previous problem. In previous problem 1’s represent land but in this problem 0’s represent land, so don’t be confused. The logic is the same.

Let’s see the code for better understanding,

class Solution {
public:
    
    void dfs(vector<vector<int>>& grid, int i, int j, int n, int m)
    {
        
        if(i < 0 || i > n-1 || j < 0 || j > m-1 || grid[i][j] == 1) return;
        
        grid[i][j] = 1;
        
        dfs(grid, i-1, j, n, m);
        dfs(grid, i+1, j, n, m);
        dfs(grid, i, j-1, n, m);
        dfs(grid, i, j+1, n, m);
        
    }
    
    int closedIsland(vector<vector<int>>& grid) {
        
        if(grid.size() == 0) return 0;
        
        int n = grid.size();
        int m = grid[0].size();
      
        int cnt = 0;
        
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++) 
            {
                if((i == 0 || j == 0 || i == n-1 || j == m-1) && grid[i][j] == 0)
                {
                    dfs(grid, i, j, n, m);
                }
            }
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++) 
            {
                if(grid[i][j] == 0)
                {
                    dfs(grid, i, j, n, m);
                    cnt++;
                }
            }
        }
        return cnt;
    }
};

The code is the similar only difference is that we first remove islands adjacent to boundary edges and then count the number of islands as we did in the previous problem.

Conclusion:


Hope code and explanation are clear to you. If you have any doubts ask int in the comment section. Thanks, For Reading Island Problems This…

That’s all folks.

Abhishek is currently pursuing CSE from Heritage Institute of Technology, Kolkata. He has a great interest in Data Structures and Algorithms, C++, Language, Competitive Coding, Android Development. His hobbies are Learning new skills, Content Writing, Competitive Coding, Teaching contents to Beginners.

Leave a Comment

Your email address will not be published. Required fields are marked *