Island Perimeter
Island Perimeter: given a grid where 1 is land and 0 is water, return the perimeter of the single island, counting every edge that borders water or the grid boundary.
- row == grid.length, col == grid[i].length
- 1 <= row, col <= 100
- grid[i][j] is 0 or 1
- There is exactly one island
Intuition
Each land cell contributes four unit edges, but any edge shared with a neighbouring land cell is interior and belongs to neither's perimeter. So the answer is 4 × land − 2 × adjacent_pairs: every shared edge is counted twice in the naive total and must be removed twice. No traversal of the island is needed — a plain sweep of the grid computes both quantities.
When a geometric quantity decomposes into per-cell contributions minus shared overlaps, counting beats traversal. The tell is that the answer depends only on local relationships, never on connectivity — which is why this problem needs no DFS despite appearing in the grid-search family.
Approach
Before reading on: work out why a shared edge must be subtracted twice rather than once. Then decide which neighbours to check so that every adjacent pair is counted exactly once.
Counting edges instead of walking the boundary
The tempting approach is to trace the island's outline, but that requires handling turns, direction, and the risk of revisiting cells. Counting is simpler and provably equivalent: the perimeter is the number of unit edges separating land from non-land. Each of the L land cells owns four edges, giving 4L before any cancellation, and every edge shared between two land cells is not part of the perimeter. Reducing the geometry to arithmetic removes the traversal entirely.
Why shared edges subtract twice
When two land cells are orthogonally adjacent, one edge sits between them. That single edge was counted once in each cell's four, so it appears twice in the 4L total and contributes zero to the perimeter — hence a subtraction of 2 per adjacent pair. Getting this coefficient wrong is the usual error: subtracting 1 per pair leaves interior edges in the answer. Counting each pair exactly once matters too, which is why the sweep checks only the neighbour above and the neighbour to the left.
The single-pass sweep and its cost
Iterate every cell. On land, add 4. Then, if the cell above is also land, subtract 2; if the cell to the left is also land, subtract 2. Looking only up and left guarantees each adjacency is discovered exactly once — the down and right relationships are the same pairs seen from the other side. Time is O(rows × cols), touching each cell once, with O(1) extra space and no recursion or visited set. An equivalent formulation adds 1 for each of the four sides that faces water or falls outside the grid.
Solution & live demo
Common pitfalls
Subtracting 1 per shared edge
if r > 0 and grid[r - 1][c] == 1:
perimeter -= 1if r > 0 and grid[r - 1][c] == 1:
perimeter -= 2The shared edge was counted once by each of the two cells, so it sits in the 4L total twice. Removing only one copy leaves every interior edge contributing 1 to the answer.
Checking all four neighbours
for dr, dc in ((-1,0),(1,0),(0,-1),(0,1)):
if neighbour is land:
perimeter -= 2check only up and left
Each adjacency is then discovered from both sides and subtracted twice as much as it should be, halving the reported perimeter on any multi-cell island.
Treating out-of-bounds as land
if grid[r - 1][c] == 1:
if r > 0 and grid[r - 1][c] == 1:
Without the bounds guard, Python's negative indexing wraps to the opposite edge of the grid and silently reads an unrelated cell, producing a wrong answer rather than an error.
Edge cases
No neighbours, so the perimeter is the full 4.
8 minus 2 for the one shared edge gives 6.
Out-of-bounds counts as water, so those edges stay in the perimeter.
16 minus 2 × 4 shared edges gives 8.
Nothing is added and the perimeter is 0.