Number of closed islands [2 solutions]
Do not miss this exclusive book on Binary Tree Problems. Get it now for free.
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:
- BFS and DFS
- Union Find
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
0sor1sdiagonally in any case. - connection can happen only in the four fundamental directions.
- the
0sin the border will never be an island as they are not covered by1sfrom all sides. - the
0sjoining the0sin 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
0we will first change it to another number lets say-1to keep track of the visited grounds. - Then we will change all
0sneighbors 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
-1as 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
return top && bottom && left && 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.
Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.