Number of Islands
Application of Union Find / Disjoint Set Union Data Structure

Algorithms and Data Structures: TheAlgorist.com

System Design: SystemsDesign.Cloud

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
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 UnionFind Series, so please be sure to go through each and every chapter in the series in order to have a solid understand of UnionFind and become really good at solving problems using UnionFind.
Please have a very good understanding of UnionFind 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 UnionFind based solution for even a complex problem when you are familiar with the implementation of UnionFind data structure discussed in the Template section of UnionFind 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 UnionFind 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 UnionFind class implementation, and build our solution on top of that.
Java Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Complexity Analysis:
Time Complexity: O(N . M . InverseAckermann(N.M)) = O(N.M) since InverseAckermann(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
UnionFind .
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn