Island / Matrix Traversal

Treat each grid cell as a graph node and each neighbor as an edge. Then islands, flood fill, enclosed regions, spreading rot and water flow are all one search, started from the right cells.

Overview

A grid is a graph

A grid problem is a graph problem in disguise. Each cell is a node. Two cells are joined when they touch along an edge, so most cells have four neighbors: up, down, left and right. Once you see that, every island question becomes a graph search, and the only decisions left are where to start the search and what to record while it runs.

| Piece | In a grid of m rows and n columns | |---|---| | node | the cell (r, c), with 0 ≤ r [!WARNING] > In Flood Fill, if the new color equals the starting color, the fill must not run: a cell recolored to the same value still looks unvisited, and the search never ends. Check that case first and return the grid unchanged.

Start from the border

Closed Islands and Number of Enclaves ask about land that cannot reach the edge. Instead of asking each island whether it touches the border, turn it around: search from every border land cell first and mark everything those searches reach. Whatever land is still unmarked is enclosed.

r = 0 — 1 — 1 — 1 — 1
r = 1 — 1 — 0 — 0 — 1
r = 2 — 1 — 1 — 1 — 1
r = 3 — 0 — 1 — 1 — 1

Here 0 is land and 1 is water, as in Closed Islands. Round one starts from the only border land cell, (3, 0), and marks it. Round two scans for unmarked land and finds (1, 1), which reaches (1, 2): one closed island. For Number of Enclaves the answer is the count of land cells left unmarked after round one instead.

Many starting points at once

Rotting Oranges asks how many minutes until every fresh orange next to a rotten one has rotted, spreading one step per minute. Put every rotten cell in the queue before the search begins. BFS then spreads from all of them together, and each ring of the search is one minute.

0 — (0, 0), already rotten
1 — (1, 0), (0, 1)
2 — (1, 1), (0, 2)
3 — (2, 1)
4 — (2, 2)

That is the grid with rows 2 1 1, 1 1 0 and 0 1 1: the answer is 4. If a fresh orange is still fresh when the queue empties, no rotten cell could reach it, and the answer is -1. The same multi-source BFS gives each cell its distance to the nearest of many sources in one pass, where one BFS per source would cost far more.

Reverse the direction

Pacific Atlantic Water Flow asks which cells can drain to both oceans, where water moves to a neighbor whose height is less than or equal to the current height. Searching downhill from every cell costs a full search per cell. Search uphill from the oceans instead: start one BFS from all Pacific border cells and one from all Atlantic border cells, moving only to neighbors that are at least as high. A cell that both searches reach drains to both oceans.

downhill from every cell — m × n — O((m × n)²)
uphill from each ocean — 2 — O(m × n)

On the 3 × 3 grid with rows 1 2 3, 8 9 4 and 7 6 5, the Pacific search reaches every cell, the Atlantic search reaches all but (0, 0) and (0, 1), so seven cells drain to both. Ask yourself the same question whenever a problem says 'from every cell': can the search run from the targets instead?

How to spot it

count regions, groups or islands — scan plus search, count the searches
largest region, area, cells reached — record a count inside the search
surrounded, enclosed, cannot reach the edge — search from the border first
spreading, minutes, nearest, shortest steps — BFS, with every source in the queue at the start
from every cell, can it reach X — reverse it and search from X
the grid changes between queries — Union-Find, which the Graphs topic covers

What you will be able to do

Turn any grid into nodes and edges and write the neighbor loop once.
Count islands and measure the biggest one with one search skeleton.
Choose between recursive DFS, an explicit stack and a queue, and say why.
Solve enclosed-region questions by searching from the border first.
Use multi-source BFS for spreading and distance questions, and reverse a search when every cell is a start.

When to use it

Counting regions of equal cells in a grid: islands, provinces, connected color patches
Measuring a region: its area, its cells, whether it touches the edge
Recoloring a connected region from one cell (flood fill)
Deciding which regions are enclosed by searching from the border first
Spreading or distance questions with many sources at once (rotting oranges, nearest exit)
Reachability from every cell, turned around into a search from the targets (water flow)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio