### 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 00000Output:1

**Example 2:**

Problem linkInput:11000 11000 00100 00011Output:3

### Video Tutorial

You can find the detailed video tutorial here### 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

### Solutions

#### Use BFS

Time Complexity: O(M*N), where M and N is row and col of grid matrix. Each grid is visited onceSpace 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 onceSpace 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 onceSpace Complexity: O(M*N) since we have to track the visited grids using a map

## No comments:

## Post a Comment

Thank your for your comment! Check out us at https://baozitraining.org/ if you need mock interviews!