200. Number of Islands

200

MediumGraph DFS and BFSDFS on a gridGrid flood fill

Number of Islands

Given an m x n grid of '1' (land) and '0' (water) characters, count the number of islands. An island is a maximal group of land cells connected horizontally or vertically; the whole grid is surrounded by water.

Open official problem prompt ↗

In plain English

Count how many distinct connected groups of land cells exist in the grid.

Picture it like this

Imagine an aerial photo of the sea dotted with land. Drop a dye that spreads across touching land tiles; every time you must start a new drop of dye, you have found another island.

Example

Input: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
Output: 3
Why: The top-left 2x2 block, the single center cell, and the bottom-right pair are three separate connected land groups.

Constraints

m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] is '0' or '1'

Pattern lesson

See the pattern, then code

Grid flood fill

↗

Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Each time you find an unvisited land cell it must start a new island, so scan the grid, and whenever you hit land, drown the entire connected region so it is never counted again.

New words, made simpleKnow these before the algorithm

Connected component: A maximal set of cells reachable from one another through allowed moves.
Flood fill: Spreading a marker outward from a start cell to all connected cells.
4-directional adjacency: Neighbors are up, down, left, right only, not diagonals.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Repeated full rescans

Re-examining the grid many times is far more work than needed.

Label each region with an id and rescan the whole grid to merge touching labels.

Time O((m*n)^2)Space O(m*n)

Best choiceDFS flood fill / sink islands

Every cell is visited a constant number of times, which is optimal.

Walk the grid once; on each new land cell, DFS to sink the whole region so it is counted only once.

Time O(m*n)Space O(m*n)

The rule we keep true

Invariant

Once DFS returns, every land cell reachable from the starting cell has been set to '0', so no future scan can re-enter that island.

Why this is correct

Reasoning

The outer scan increments the count exactly once per island because the first cell of each island triggers a DFS that erases the entire island before the scan can reach any of its other cells.

The algorithm in three movesSay these aloud before coding

1Scan every cell of the grid

count = 1 after sinking top-left block

2When you meet an unvisited '1', increment the island count

dfs flips grid[0][0],[0][1],[1][0],[1][1] to '0'

3Run DFS from that cell, flipping every reachable '1' to '0' to mark it visited

count = 3 after all scans

4Continue the scan; each fresh '1' starts exactly one new island

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readgrid[0][0] == '1'

2 · AskNew land not yet visited?

3 · Update statecount = 0 -> 1

4 · ResultStart DFS, sink the top-left 2x2 block

Key takeaway

A row fragment: two adjacent land cells form one island; the isolated land cell to the right is another.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 7-15Recursive sink helper
Returns immediately off-grid or on water; otherwise marks the cell water and recurses into all four neighbors.
2
Lines 17-21Main scan
Each newly seen '1' bumps the count and triggers a full sink of its island.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Grid that is all water returns 0
Grid that is all land returns 1
Single row or single column grids
A 1x1 grid

Common beginner mistakes

Forgetting to mark cells visited, causing infinite recursion
Counting diagonal neighbors as connected
Deep recursion can overflow the stack on a fully-land 300x300 grid; an explicit stack or BFS avoids it

Check your understanding

Why is it safe to mutate the input grid instead of keeping a separate visited set?

PyPython 3 · solution.py

Optimal

1class Solution:2    def numIslands(self, grid: list[list[str]]) -> int:3        if not grid:4            return 05        rows, cols = len(grid), len(grid[0])6        count = 078        def dfs(r: int, c: int) -> None:9            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":10                return11            grid[r][c] = "0"12            dfs(r + 1, c)13            dfs(r - 1, c)14            dfs(r, c + 1)15            dfs(r, c - 1)1617        for r in range(rows):18            for c in range(cols):19                if grid[r][c] == "1":20                    count += 121                    dfs(r, c)22        return count

Time complexityO(m * n)Optimized

Space complexityO(m * n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMetaGoogleMicrosoft

Number of Islands

Number of Islands

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Graph DFS and BFS