70. Number of Islands

Medium · Graph

Given an m × n 2D grid where each cell is either '1' (land) or '0' (water), count the number of distinct islands. An island is formed by connecting adjacent lands horizontally or vertically (not diagonally). Each cell is considered a separate island if it is surrounded by water or the grid boundary.

You must find the total count of islands in the grid.

Examples

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
Explanation: All the '1's form a single connected island. Starting from any '1', you can reach all other '1's by moving up, down, left, or right.
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
Explanation: There are three islands: one in the top-left (2×2), one in the middle (1×1), and one in the bottom-right (1×2).

Constraints