#200

Number of Islands

specialist · 645 · lc medium +30 · verified · 63.9% accepted · 24,843 likes · top 67%

⚑ DFS / BFS: Connected Components & Reachability⚑ Disjoint Set Union
play →

Description

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), count and return the number of distinct islands.

An island is a group of '1' cells connected horizontally or vertically. The entire border of the grid is 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

Code

1
2
3