Island Perimeter — Solution

Problem

You are given a 2D grid where each cell is either land (1) or water (0), and the grid contains exactly one island with no interior lakes. Find the total perimeter of that island — the number of land cell edges that border water or the grid boundary.

Example:

• Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
• Output: 16
• Explanation: The connected island has 7 land cells; after accounting for 6 shared borders, the perimeter is 7×4 − 6×2 = 16.

Intuition

Every land cell contributes 4 sides to the perimeter. Whenever two land cells sit next to each other, they share a border that should not be counted — so each shared edge subtracts 2 from the running total (one side from each neighbor). The trick is to only check rightward and downward neighbors while scanning left-to-right, top-to-bottom: this way each shared border is visited exactly once, so we subtract exactly 2 per pair without any double-counting.

Solution — Linear Scan

Scan every cell once. For each land cell add 4, then subtract 2 for each shared border with an immediately right or immediately below neighbor.

1. Initialize perimeter = 0.
2. Iterate over every cell (row, col) in the grid.
3. If grid[row][col] == 1, add 4 to perimeter.
4. If the cell to the right (col + 1) is in bounds and also land, subtract 2.
5. If the cell below (row + 1) is in bounds and also land, subtract 2.
6. Return perimeter.

1def islandPerimeter(grid: list[list[int]]) -> int:
2    rows, cols = len(grid), len(grid[0])
3    perimeter = 0
4
5    for row in range(rows):
6        for col in range(cols):
7            if grid[row][col] == 1:
8                perimeter += 4  # every land cell starts with 4 exposed sides
9
10                # check only right and down so each shared edge is counted once
11                if col + 1 < cols and grid[row][col + 1] == 1:
12                    perimeter -= 2  # shared vertical edge cancels one side from each cell
13                if row + 1 < rows and grid[row + 1][col] == 1:
14                    perimeter -= 2  # shared horizontal edge cancels one side from each cell
15
16    return perimeter

Time: O(m × n) — single pass over all cells in the grid.
Space: O(1) — no extra data structures; the grid is read but not modified.

Complexity Summary

Common Mistakes

• Subtracting 1 instead of 2 per shared edge — two adjacent land cells each lose one exposed side, so the net reduction is 2 per shared border, not 1.
• Checking all 4 directions and subtracting 1 each — this is equivalent but requires bounds checking in every direction; only checking right and down during a left-to-right scan handles each border exactly once.
• Skipping bounds checks before indexing — accessing grid[row][col + 1] when col is the last column causes an index-out-of-bounds error; always guard with col + 1 < cols first.
• Using DFS with a visited set — a DFS traversal is valid but uses O(m × n) space and extra bookkeeping with no benefit over a plain scan.
• Counting diagonal neighbors — only the 4 cardinal directions (up, down, left, right) share grid edges; diagonal cells share only a point and do not affect perimeter.

Related Problems

• flood-fill — grid traversal where connected land cells are processed as a group
• max-area-of-island — counts the total cells in the largest island instead of its perimeter
• number-of-islands — uses the same 4-directional adjacency pattern to count distinct islands
• surrounded-regions — grid connectivity where border-reachable cells are treated differently from interior cells
• rotting-oranges — grid BFS problem that uses the same right/down neighbor-checking logic