Leetcode solution 200. Number of Islands (Using BFS, DFS & Disjoint Set)

Problem Statement 

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:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

 Problem link

Video Tutorial

You can find the detailed video tutorial here

• Youtube BFS & DFS solution in 2015
  
• Youtube Disjoint Solution
  
• B站

Thought Process

I have recorded a video back in 2015 (5 years ago, Geez time flies) using BFS and DFS. The essential idea is every time we see a land (i.e., "1"), we would trigger a BFS or DFS search to mark all the connected grids and increase the island counts to 1.

Another solution is to use Disjoint Set (aka Union Find). There is a generic solution where we could implement a DisjointSet data structure and perform "union" steps first to assign each grid a "parent". In the 2nd iteration we can perform "find" step to count how many distinct "parents", which is the number of islands.

A quick summary of some classic use cases

• Disjoint Set / Union Find (Disjoint set is the data structure while union find is the algorithm, people normally use it interchangeably)  can often be used to solve if a graph is connected or not, such as phone contact problem (who knows who, how many isolated groups are there)
  
• To detect if a directed graph has cycle, use Kahn's algorithm for topological sort
• To detect if a un-directed graph has cycle
• We could use normal BFS or DFS
  
• We should use Union Find with edge list graph representation
  

Solutions

Use BFS

Time Complexity: O(M*N), where M and N is row and col of grid matrix. Each grid is visited once
Space Complexity: O(M*N) since we have to track the visited grids

Use DFS

Time Complexity: O(M*N), where M and N is row and col of grid matrix. Each grid is visited once
Space Complexity: O(M*N) since we have to track the visited grids

Use Disjoint Set / Union Find

Time Complexity: O(M*N), where M and N is row and col of grid matrix. Each grid is visited once
Space Complexity: O(M*N) since we have to track the visited grids using a map

References

• Leetcode official solution