158. Number of Islands

MediumGraph

Given an m x n 2D grid map of '1's (land) and '0's (water), return the number of islands. Grid is given as an array of strings.

Examples

Example 1

Input: grid = ["11110","11010","11000","00000"]

Output: 1

Explanation: All the 1s are joined up, down, left or right into one connected block of land, so there is 1 island.

Example 2

Input: grid = ["11000","11000","00100","00011"]

Output: 3

Explanation: There are three separate groups of 1s: a 2 x 2 block in the top-left, a single cell in the middle and a pair in the bottom-right. That is 3 islands.

Example 3

Input: grid = ["0"]

Output: 0

Explanation: The grid is all water, so there are no islands.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 300

How to solve Number of Islands: approach and complexity

DFS Flood Fill: O(m · n) time, O(m · n) recursion space.
BFS Flood Fill (optimal): O(m · n) time, O(min(m, n)) space.

Same flood-fill idea as DFS, but iterative — a queue replaces the recursion stack. The big practical win: on a long thin grid (say 1×10000) DFS would blow Python's recursion limit, while BFS stays comfortable.

Watch it run step by step