LeetCode 463: Island Perimeter

Problem Restatement

We are given a rectangular grid.

Each cell is either:

1  # land
0  # water

The grid contains exactly one island. Land cells connect horizontally or vertically, not diagonally. The grid is surrounded by water, and the island has no lakes. We need to return the perimeter of the island.

A land cell is a square with side length 1.

So one isolated land cell has perimeter:

4

When two land cells touch, they share one edge. That shared edge is no longer part of the outside perimeter.

Input and Output

Function shape:

def islandPerimeter(grid: list[list[int]]) -> int:
    ...

Examples

Example 1:

grid = [
    [0, 1, 0, 0],
    [1, 1, 1, 0],
    [0, 1, 0, 0],
    [1, 1, 0, 0],
]

The answer is:

16

This is the standard example from the problem statement.

Example 2:

grid = [[1]]

There is one land cell and no neighboring land.

Its perimeter is:

4

Example 3:

grid = [[1, 0]]

There is one land cell touching water on the right and grid boundary on the other sides.

The perimeter is:

4

First Thought: Count Exposed Sides

The perimeter is made of land-cell edges that touch water or the grid boundary.

So for each land cell, we can inspect its four directions:

up
down
left
right

For each direction:

1. If the neighbor is outside the grid, add 1.
2. If the neighbor is water, add 1.
3. If the neighbor is land, add 0.

This is direct and easy to reason about.

class Solution:
    def islandPerimeter(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        perimeter = 0

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 0:
                    continue

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if nr < 0 or nr == rows or nc < 0 or nc == cols:
                        perimeter += 1
                    elif grid[nr][nc] == 0:
                        perimeter += 1

        return perimeter

This works because it counts exactly the outside edges of land cells.

Problem With This Approach

This approach is already efficient.

It scans every cell once and checks four directions.

The time complexity is:

O(rows * cols)

That is optimal because we may need to inspect the whole grid.

However, there is an even simpler counting formula.

Each land cell starts with 4 edges.

Whenever two land cells are adjacent, they share one edge.

That shared edge removes 2 from the total perimeter: one edge from the first cell and one edge from the second cell.

Key Insight

For every land cell:

perimeter += 4

Then for each shared edge between two land cells:

perimeter -= 2

To avoid counting the same shared edge twice, we only check two directions for each land cell:

down
right

If the cell below is land, subtract 2.

If the cell to the right is land, subtract 2.

This counts every adjacent land pair exactly once.

Algorithm

Initialize:

perimeter = 0

Loop through every cell.

If the current cell is water, skip it.

If it is land:

1. Add 4.
2. If the cell below is land, subtract 2.
3. If the cell to the right is land, subtract 2.

Return perimeter.

Walkthrough

Use a small grid:

grid = [[1, 1]]

There are two land cells.

Start:

perimeter = 0

First land cell:

perimeter += 4

It has a right neighbor that is also land, so:

perimeter -= 2

Now:

perimeter = 2

Second land cell:

perimeter += 4

No right or down land neighbor.

Final:

perimeter = 6

This is correct because a 1 x 2 rectangle has perimeter 6.

Correctness

Each land cell contributes four sides before considering neighboring land cells.

If two land cells are adjacent, the edge between them is internal. It cannot be part of the island’s outside perimeter.

The algorithm subtracts 2 for each adjacent land pair: one side from each of the two cells.

By checking only the down and right neighbors, each adjacent land pair is counted exactly once.

Therefore, after all land cells are processed, the remaining count is exactly the number of land-cell sides touching water or the grid boundary.

That is the island perimeter.

Complexity

Let:

rows = len(grid)
cols = len(grid[0])

Implementation

class Solution:
    def islandPerimeter(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        perimeter = 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 0:
                    continue

                perimeter += 4

                if r + 1 < rows and grid[r + 1][c] == 1:
                    perimeter -= 2

                if c + 1 < cols and grid[r][c + 1] == 1:
                    perimeter -= 2

        return perimeter

Code Explanation

We first read the grid dimensions:

rows = len(grid)
cols = len(grid[0])

Then we scan each cell:

for r in range(rows):
    for c in range(cols):

Water cells do not contribute to the perimeter:

if grid[r][c] == 0:
    continue

Each land cell begins with four exposed sides:

perimeter += 4

If there is land below, the current cell and the lower cell share an edge:

if r + 1 < rows and grid[r + 1][c] == 1:
    perimeter -= 2

If there is land to the right, they also share an edge:

if c + 1 < cols and grid[r][c + 1] == 1:
    perimeter -= 2

Finally:

return perimeter

returns the outside perimeter.

Alternative DFS View

We can also compute the perimeter by DFS.

From each land cell, explore four directions.

Whenever exploration steps into water or outside the grid, that direction contributes 1 to the perimeter.

This version matches the geometric definition directly.

class Solution:
    def islandPerimeter(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        seen = set()

        def dfs(r: int, c: int) -> int:
            if r < 0 or r == rows or c < 0 or c == cols:
                return 1

            if grid[r][c] == 0:
                return 1

            if (r, c) in seen:
                return 0

            seen.add((r, c))

            return (
                dfs(r + 1, c)
                + dfs(r - 1, c)
                + dfs(r, c + 1)
                + dfs(r, c - 1)
            )

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    return dfs(r, c)

        return 0

The counting solution is shorter and uses constant extra space, so it is usually the preferred answer.

Testing

def run_tests():
    s = Solution()

    assert s.islandPerimeter([
        [0, 1, 0, 0],
        [1, 1, 1, 0],
        [0, 1, 0, 0],
        [1, 1, 0, 0],
    ]) == 16

    assert s.islandPerimeter([[1]]) == 4
    assert s.islandPerimeter([[1, 0]]) == 4
    assert s.islandPerimeter([[1, 1]]) == 6
    assert s.islandPerimeter([[1], [1]]) == 6

    assert s.islandPerimeter([
        [1, 1],
        [1, 1],
    ]) == 8

    assert s.islandPerimeter([
        [0, 0, 0],
        [0, 1, 0],
        [0, 0, 0],
    ]) == 4

    print("all tests passed")

run_tests()

Test meaning: