Island Perimeter: Counting Edges Without DFS

LeetCode 463: Island Perimeter gives you a 2D grid where 1 represents land and 0 represents water. The grid contains exactly one island (one or more connected land cells), and there are no lakes (water inside the island). Your job is to return the perimeter of that island.

You might reach for DFS or BFS, but you do not need any graph traversal here. A single scan through the grid with some simple counting is all it takes.

The problem

You are given an m x n grid of integers where each cell is either 0 (water) or 1 (land). The island has no lakes and is fully connected. Return the total perimeter of the island.

Why this problem matters

Island Perimeter is a gentle entry point into matrix traversal problems. It teaches you to think about cells and their neighbors, which is the same foundation you will use for flood fill, number of islands, and surrounded regions. The twist here is that you do not need recursion or a visited set. You just need to count carefully.

This problem also shows up as a building block in interviews: the idea of "start with a maximum and subtract overlap" appears in interval merging, rectangle area calculations, and many other contexts.

The key insight

Every land cell is a square with 4 edges. If that cell were alone, it would contribute 4 to the perimeter. But when two land cells share a side, the edge between them is internal, not part of the perimeter. Each shared side removes 2 from the total (one edge from each cell).

So the formula is:

perimeter = (land_cells * 4) - (shared_edges * 2)

To count shared edges without double counting, you only check two directions per cell: right and down. If the cell to the right is also land, that is one shared edge. If the cell below is also land, that is another. By only looking right and down, each pair of adjacent cells gets counted exactly once.

The code

def islandPerimeter(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    land = 0
    shared = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                land += 1
                if r + 1 < rows and grid[r + 1][c] == 1:
                    shared += 1
                if c + 1 < cols and grid[r][c + 1] == 1:
                    shared += 1
    return land * 4 - shared * 2

Why this works

You scan every cell once. For each land cell, you add 1 to land. Then you check the cell below and the cell to the right. If either is also land, you have found a shared edge and increment shared. At the end, every land cell contributes 4 edges, and every shared edge removes 2. The result is the exact perimeter.

This avoids any recursion, any visited tracking, and any stack or queue. The algorithm is purely arithmetic.

Visual walkthrough

The walkthrough shows the process on the example grid [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]. With 7 land cells and 6 shared edges, the perimeter is 7 * 4 - 6 * 2 = 16.

Complexity analysis

Time: You visit every cell exactly once and do constant work per cell (checking at most two neighbors). That is O(m * n).

Space: You use two integer counters. No recursion stack, no visited array, no queue. That is O(1) extra space.

Building blocks

Grid neighbor checking

The pattern of checking adjacent cells in a grid appears in almost every matrix problem. Here you only need right and down, but the general 4-direction check (up, down, left, right) is the same idea:

for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        # process neighbor

Once this pattern is automatic, problems like flood fill, rotting oranges, and shortest path in a grid become much easier to set up.

Counting by subtraction

Instead of directly counting perimeter edges (which requires checking all four sides of every land cell against boundaries and water), you start with the theoretical maximum and subtract overlap. This "assume the best, then correct" approach is cleaner and less error-prone. You will see the same idea in problems like rectangle area (sum of two rectangles minus intersection) and merge intervals (total length minus overlap).

Edge cases

• Single cell island: one land cell, zero shared edges. Perimeter is 1 * 4 - 0 = 4.
• Straight line island: a 1 x n strip of land cells has n - 1 shared edges. Perimeter is n * 4 - (n - 1) * 2 = 2n + 2.
• Full grid of land: every interior cell shares 4 edges. The perimeter equals 2 * (m + n), which is just the outer boundary of the rectangle.
• L-shaped or irregular islands: the formula still works because it counts every adjacent pair exactly once regardless of shape.

From understanding to recall

The formula land * 4 - shared * 2 is simple enough to derive on the spot, but under interview pressure you want it to be instant. The piece that trips people up is the "only check right and down" trick for avoiding double counts. Practice writing the solution from scratch: the nested loop, the two neighbor checks, the final formula. Do it today, tomorrow, and again in a few days. After a handful of reps, you will not even have to think about which directions to check.

Grid counting and neighbor checking are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them in isolation and reinforcing them with spaced repetition is far more effective than grinding random problems.

Related posts

• Number of Islands - Grid DFS for connected components, the natural next step after simple grid counting
• Surrounded Regions - Another grid boundary problem where you need to distinguish interior from exterior
• Game of Life - Neighbor counting in a grid with in-place state transitions