🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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

Note: This problem is part of Union-Find Series, so please be sure to go through each and every chapter in the series in order to have a solid understand of Union-Find and become really good at solving problems using Union-Find.

Please have a very good understanding of Union-Find Fundamentals before solving this problem. Through all the problems discussed in Problem Solving using Union Find one of my goals is to show you how easy it becomes writing an Union-Find based solution for even a complex problem when you are familiar with the implementation of Union-Find data structure discussed in the Template section of Union-Find Fundamentals chapter.

Solution:

Look how each island is a connected component or disjoint set on its own.
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]

Once you get this you know what to do next: find all the connected components or disjoint sets. You could achieve this by two ways:
(1) running a DFS or Depth First Search to find all the connected components and then return the number of connected components we found,
OR,
(2) use Union-Find data structure and return the total number of disjoint sets found.

We would scan the given grid row by row (left to right) top to bottom, and for every cell with '1' encountered:
(1) unionize with the cell immediately above it if the above cell contains '1'
(2) unionize with the left adjacent cell if the left cell contains '1'

We do not need to unionize with vertically below and horizontally right cells, since they would be processed eventually anyways.

We would be reusing our standard Union-Find class implementation, and build our solution on top of that.

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Complexity Analysis:

Time Complexity: O(N . M . Inverse-Ackermann(N.M)) = O(N.M) since Inverse-Ackermann(N.M) = O(1) approximately

Space Complexity: O(N.M), since union find data structure would need O(M.N) space to store all N.M elements. where given grid is of dimension N X M.

Please be sure to take a serious look at all the problems discussed in Union Find Problems to become from good to GREAT in solving problems using Union-Find .

Instructor: