Count Islands
mediumSave
Depth-First SearchGraphMatrixUnion Find
Given a 2D grid map consisting 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
[ [ "1", "1", "1", "1", "0" ], [ "1", "1", "0", "1", "0" ], [ "1", "1", "0", "0", "0" ], [ "0", "0", "0", "0", "0" ] ]
Output
1
Explanation. There is one large island in the top left corner.
Example 2
Input
[ [ "1", "1", "0", "0", "0" ], [ "1", "1", "0", "0", "0" ], [ "0", "0", "1", "0", "0" ], [ "0", "0", "0", "1", "1" ] ]
Output
3
Explanation. There are three separate islands. Two small islands in the bottom and a large one on the top.
Follow-up: Can you solve this problem using DFS (Depth-First Search) or BFS (Breadth-First Search) techniques?
Constraints:
The number of rows and columns of the input matrix will each be in the range [1, 300]. Each element in the matrix will be either '0' or '1'.
- Views
- 4