Islands in a grid: neighbours and edges
Lesson 10 of 11
10Islands in a grid: neighbours and edges
The big pictureA grid is a hidden graph: each cell is a node and its four neighbours are edges. Most grid problems are "walk the cells and look at the neighbours".
What the picture shows: The core loop of any grid problem. Only what you do with each neighbour changes.
Map of this part
The concepts in order, click any one to jump to it:
Two ways into the same idea
Picture a map of squares: green is land and blue is water. To know how many islands there are, start from any green square and colour every green connected to it, then look for green not yet coloured. Each time you start a new colouring you have found a new island.
Directions [(1,0),(-1,0),(0,1),(0,-1)], and the check 0 <= nr < rows and 0 <= nc < cols. DFS with an explicit stack avoids Python's recursion limit on big grids. Time is O(rows × cols) since each cell is visited once. For the perimeter: each land cell has 4 edges, and an edge shared with another land cell does not count; put another way, 4 × land − 2 × adjacent pairs.
Before You Start
🔁Nested loops
You walk rows and columns.
🗂️The stack
You know push and pop.
The Core Idea
1Neighbours and bounds
Write the four directions in a list and check bounds before reading any cell. This counts the land neighbours of each cell:
grid = [[0, 1, 0],
[1, 1, 1],
[0, 1, 0]]
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
rows, cols = len(grid), len(grid[0])
def land_neighbours(r, c):
count = 0
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
count += 1
return count
print(land_neighbours(1, 1), land_neighbours(0, 1))grid[-1] raises no error but returns the last row! Without the bounds check a neighbour "off the map" becomes a cell from the other side.2Counting islands with depth-first search
Each unvisited land cell starts a new island. We colour the whole island with a stack so it is not counted again, and measure its area along the way:
grid = [[1, 1, 0, 0],
[1, 0, 0, 1],
[0, 0, 1, 1],
[0, 0, 0, 1]]
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
rows, cols = len(grid), len(grid[0])
seen = set()
def explore(r, c):
stack, area = [(r, c)], 0
seen.add((r, c))
while stack:
r, c = stack.pop()
area += 1
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in seen:
seen.add((nr, nc))
stack.append((nr, nc))
return area
areas = [explore(r, c) for r in range(rows) for c in range(cols)
if grid[r][c] == 1 and (r, c) not in seen]
print("islands:", len(areas), "areas:", areas)3Exercise: the perimeter
The perimeter is the number of land edges touching water or the map's border. No DFS needed here: walk every land cell, add 4, and subtract 1 for each land neighbour (use land_neighbours above). Test: a single land cell has perimeter 4, two adjacent cells have 6, and the cross grid in the first example has 12.
Worked example
Problem: a single row [[1,1,1]]. Analysis: 3 cells × 4 = 12 edges. Adjacent pairs: (0,0)-(0,1) and (0,1)-(0,2), each pair hiding two edges. Answer: 12 − 4 = 8, the perimeter of a 3×1 rectangle.
Myth vs Reality
| Myth | Reality |
|---|---|
| Diagonal cells are neighbours. | In most problems there are only four neighbours. Read the definition; some problems count eight. |
| Recursion is always easier for DFS. | Shorter, but it hits Python's recursion limit on big grids. An explicit stack is safe. |
Where you meet it at work
🗺️Maps
Connected regions in satellite images.
🎨The paint bucket tool
Filling a connected area with one colour.
Test your understanding
What is the perimeter of two horizontally adjacent land cells?
4+4 minus two shared edges = 6.
Why mark visited cells?
Without marking, the search returns to the same cells forever.
What is the time to count islands?
Each cell is visited once and its four neighbours checked.
Quick review cards
Check Your Understanding
What does grid[-1] give in Python?
The last row, not an error. That is why the bounds check is essential.
Do you need DFS for the perimeter?
No, walking every cell and counting its neighbours is enough.
How would you count a diagonal neighbour if asked?
Add the four diagonal directions to DIRS.
Resources for this lesson
Grouped by type. Start with the official docs for precision, or an article or video for the explanation.
Done with this lesson?
Sign in to save your progress.