Number of Islands

Given an R × C grid of 1s (land) and 0s (water), return the number of islands. An island is a maximal group of 1s connected 4-directionally (up, down, left, right). The grid's borders are surrounded by water.

Hints

· Stuck? Reveal one nudge at a time.

Treat the grid as a graph: each land cell connects to its 4 orthogonal land neighbours.

Scan for an unvisited land cell — that's a new island — then flood it.

Sink flooded land to 0 to mark it without a separate visited array.

Common doubts

Both are O(R·C) and give the same count. BFS (iterative) avoids stack overflow when a single island fills a large grid.

Once a land cell is counted as part of an island, it never needs to be revisited, so overwriting it with water is fine.

Yes — union adjacent land cells and count the land components; useful when cells are added incrementally (islands II).

Interview follow-ups

· What an interviewer asks next.

Add the 4 diagonal directions to the neighbour set — 8-directional flood.

Union-Find (Islands II): union each new land cell with adjacent land and track the running count.

Fun facts

LeetCode 200 — the canonical grid-flood problem behind dozens of variants.
The 'sink the island' trick is the grid analogue of a visited array.

Asked at

AmazonMicrosoftGoogleFacebook

Frequently Sometimes Occasionally

Example 1

Input: grid = [[1,1,0],[0,1,0],[0,0,1]]
Output: 2
One L-shaped island and one single-cell island.

Example 2

Input: grid = [[0,0],[0,0]]
Output: 0
All water.

Constraints

- 1 <= R, C <= 300 - grid[i][j] is 0 or 1

An island is a connected component of land in a grid-graph, where each land cell is adjacent to its up/down/left/right land neighbours. Scan the grid; whenever you hit an unvisited land cell, that's a new island — flood the entire island so it isn't counted again.

Flooding can be DFS (recursion) or BFS (a queue); both visit every cell of the island once. A neat trick to avoid a separate visited array: sink each land cell to 0 as you visit it. Total work is O(R·C) — every cell is touched a constant number of times.

Prerequisites

Before you start

· Concepts used directly in the solution.

Grid as graph. a cell's neighbours are its 4 orthogonal cells.

Flood fill. visit and mark an entire connected region.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“4-directional or 8-directional?”

4-directional here (up/down/left/right).

“Can I modify the grid?”

Yes — sinking visited land to 0 avoids a separate visited array.

The ideal opening — say it like this

I scan the grid; each unvisited land cell starts a new island, and I flood it to mark the whole island.

Sinking visited cells to 0 keeps it O(R·C) with no extra visited array.

Understand the problem

Worked example — grid [[1,1,0],[0,1,0],[0,0,1]]

(0,0) land -> island 1, flood {(0,0),(0,1),(1,1)}
(2,2) land -> island 2, flood {(2,2)}
answer = 2

Key observations

1Aha

Islands are connected components

Of the grid-graph where land cells link to orthogonal land.

2Aha

Sink to avoid a visited array

Setting visited land to 0 marks it in place.

3Aha

O(R·C) total

Each cell is visited a constant number of times.

Brute force vs optimal

	DFS flood	BFS flood
Container	recursion / stack	queue
Time	O(R·C)	O(R·C)
Risk	deep recursion on huge islands	none (iterative)

Both count the same islands; BFS avoids deep recursion. Full code is in the Approaches selector below.

Summary

Key takeaway

Scan the grid; each unvisited land cell is a new island — flood it (DFS or BFS), sinking cells to 0. O(R·C) time.

for each cell:
    if land: count++, flood(cell)   # sink flooded land to 0