×

Search anything:

# Number of closed islands [2 solutions]

#### Algorithms Graph Algorithms union find

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article, we have explored how to find the Number of closed islands in a graph. We have presented two approaches using the concept of BFS/ DFS and Union Find.

Pre-requisites:

## Problem Statement

Given a 2-D 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.

Example:

Output: 2

Explanation: Here the `0s` which are marked inside the box are only considered to be closed islands as they are completely surrounded by `1s` and follows the rest of the conditions

## Observations

So from the question and the example we can say the following:

• we can't connect `0s` or `1s` diagonally in any case.
• connection can happen only in the four fundamental directions.
• the `0s` in the border will never be an island as they are not covered by `1s` from all sides.
• the `0s` joining the `0s` in the border can never be a part of a closed island.

Now lets solve it.

## Approach 1

In this approach we will discuss a way to solve this problem using BFS/DFS. We will follow the following steps to solve it.

• We will start our iteration from `grid[1][1]` as we don't have to consider the border elements.
• Once we encounter a `0` we will first change it to another number lets say `-1` to keep track of the visited grounds.
• Then we will change all `0s` neighbors horizontally or vertically from the current ground using a recursive function.
• The recursive function will return true if that cell is visited or if its a `1`
• If its a ground not visited then it will return false if its out of boundary.
• Then it would change the cells value to `-1` as we have visited it and then call the recursive function in all four direction.
• Then it would return the `&&` value of all directions.

Let's look at the code it understand it better.

``````#include <iostream>
#include <vector>

using namespace std;

bool isClosedIsland(vector<vector<int>> &grid, int i, int j, int r, int c)
{
if (grid[i][j] == 1 || grid[i][j] == -1)
return true;
if (i <= 0 || i >= r - 1 || j <= 0 || j >= c - 1)
return false;
grid[i][j] = -1;

bool top = isClosedIsland(grid, i - 1, j, r, c);    // Top
bool bottom = isClosedIsland(grid, i + 1, j, r, c); // Bottom
bool left = isClosedIsland(grid, i, j - 1, r, c);   // Left
bool right = isClosedIsland(grid, i, j + 1, r, c);  // Right

}

int closedIsland(vector<vector<int>> &grid)
{
if (grid.size() == 0)
return 0;
int cnt = 0, r = grid.size(), c = grid[0].size();
for (int i = 1; i < r - 1; i++)
{
for (int j = 1; j < c - 1; j++)
{
if (grid[i][j] == 0)
{
if (isClosedIsland(grid, i, j, r, c))
{
cnt++;
}
}
}
}
return cnt;
}

int main()
{
int r, c;
cin >> r >> c;
vector<vector<int>> grid(r, vector<int>(c));
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
cin >> grid[i][j];
}
}
cout << closedIsland(grid) << endl;
return 0;
}
``````

The time and space complexity of the above approach will be `O(r*c)`, where `r` is the number of rows and `c` is the number of columns in the matrix.

## Approach 2

Here in this approach we will taking an insightful approach using union find.

First we would accept the vector and then `numIslands()` is called. Inside `numsIsland` first we will make all the lands or `0s` in the border, and the ones having connection to those in horizontal and vertical direction of the grid will be converted to `1s` or any other number as you wish. We will be doing this with `changeCorner()` and recursively calling `change()` inside it. The reason why we are doing this is in the observation section, ie, those elements will never be a part of a closed island. So the remaining zeros after this step will be a part of a closed island or itself be one.

So after this we will initialize a vector of pairs `edges`, we will use this to store all the connections a particular ground or `0` have with adjacent cells in right and downward direction.
Now we will iterate through the grid again, this time when we encounter a `0` we will calculate a unique `id` for that cell using the formula `i*n+j` and will check if the cells in both direction are `0s` or not, if its there then we will calculate an id for both of them and will push `id, right_id` and `id, down_id` into the vector. For the above grid the following will be the `edges` vector.

``````                                1 1 1 1 1 1 1 1               9  10
1 0 0 0 0 1 1 1               9  17
1 0 1 0 1 1 1 1    --->      10  11
1 0 0 0 0 1 0 1              11  12
1 1 1 1 1 1 1 1              11  19
17  25
19  27
25  26
26  27
27  28
``````

Now we will form another vector of size `r*c` where `r` and `c` are the rows and columns of the grid. This vector would act as a hash vector, so we will call it a `hashSet`. We will initialize the value of `hashSet` with the values of `i`. Then we will iterate through the edges vector and use `Union()` for each of the pair. In `Union()` we will use `find()` for each element in the pair. The `find()` uses the passed value and the `hashSet` to find the root or starting of the island chain. If the value and the `hashSet` value are equal then it would return the same value else it uses the `while()` loop to find the starting of the chain. If the root value of both the edges are different then we change the values in the `hashSet`, this is done from the `Union()` itself, since they are adjacent and part of the same chain. By the end of this step the starting node `id's` index inside the `hashSet` will have same value as its index and the rest of them will have the index value of other nodes which would connect them with these starting nodes. The following is the `hashSet` value for the given grid.

``````0 1 2 3 4 5 6 7 8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
0 1 2 3 4 5 6 7 8 10 17 12 19 13 14 15 16 11 18 25 20 21 22 23 24 27 28 26 28 29 30 31 32 33 34 35 36 37 38 39
``````

Now we will count the elements, for this we will traverse through the grid again and for each `0` we encounter we will check if the `hashSet[i]==i` if it is that means that `0` is the starting point of the island chain and we will increment the value by one. Here we use an interesting technique to iterate through the `grid` and the `hashSet` at the same time. By the end of this step we will have the count of closed islands in the given grid.

Note: If you check carefully if one `0` is being surrounded by `1s` in all sides then it was not considered in the `hashSet`, but in this step we will count all those type of `0s`.

``````#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

void change(vector<vector<int>> &grid, int x, int y, int c, int r)
{
if (x < 0 || y < 0 || x > r - 1 || y > c - 1 || grid[x][y] == 1)
return;

grid[x][y] = 1;

change(grid, x + 1, y, c, r);
change(grid, x, y + 1, c, r);
change(grid, x - 1, y, c, r);
change(grid, x, y - 1, c, r);
}

void changeBorder(vector<vector<int>> &grid)
{
int r = grid.size();
int c = grid[0].size();

for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
if (i * j == 0 || i == r - 1 || j == c - 1)
{
if (grid[i][j] == 0)
{
change(grid, i, j, c, r);
}
}
}
}
}

int findRoot(vector<int> &hashSet, int val)
{
while (val != hashSet[val])
{
val = hashSet[val];
}

return val;
}

void Union(vector<int> &hashSet, int first, int second)
{
int first_root = findRoot(hashSet, first);

int second_root = findRoot(hashSet, second);

if (first_root != second_root)
hashSet[first_root] = second_root;
}

int closedIslands(vector<vector<int>> &grid)
{

if (grid.size() == 0)
return 0;

int r = grid.size();
int c = grid[0].size();

changeBorder(grid);

vector<pair<int, int>> edges;

for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{

if (grid[i][j] == 0)
{
int id = i * c + j;

if (j + 1 < c)
{

if (grid[i][j + 1] == 0)
{
int right = i * c + j + 1;
edges.push_back({id, right});
}
}
if (i + 1 < r)
{

if (grid[i + 1][j] == 0)
{
int down = (i + 1) * c + j;
edges.push_back(make_pair(id, down));
}
}
}
}
}

vector<int> hashSet(r * c, 0);
for (int i = 0; i < r * c; i++)
{
hashSet[i] = i;
}

for (auto edge : edges)
{
Union(hashSet, edge.first, edge.second);
}

int numComponents = 0;

for (int i = 0; i < r * c; i++)
{
if (grid[i / c][i % c] == 0 && hashSet[i] == i)
numComponents++;
}

return numComponents;
}

int main()
{
int r, c;
cin >> r >> c;
vector<vector<int>> grid(r, vector<int>(c));
for (int i = 0; i < r; i++)
{
for (int j = 0; j < c; j++)
{
cin >> grid[i][j];
}
}

cout << closedIslands(grid);
return 0;
}
``````

The time and space complexity of the above program will be `O(r*c)`

By now you would have a complete understanding of how to solve this problem.

#### Aswin Shailajan

Aswin Shailajan is a B. Tech Computer Science student at Vellore Institute of Technology and is a SDE, Intern at OpenGenus.

Improved & Reviewed by:

Number of closed islands [2 solutions]