Island Perimeter

Difficulty: Easy Source: NeetCode

Problem

You are given a row x col grid grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

Return the perimeter of the island.

Example 1: Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]] Output: 16

Constraints:

• row == grid.length, col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] is 0 or 1
• There is exactly one island in grid

Prerequisites

Before attempting this problem, you should be comfortable with:

• 2D grid traversal — iterating over every cell with row/col indices
• Neighbor checking — looking at the four adjacent cells of a given cell

1. Brute Force

Intuition

For each land cell, start with 4 potential perimeter edges. Then for each of the four neighbors, if that neighbor is also land, the shared edge is interior and not part of the perimeter — subtract 1. Summing this over all land cells gives the total perimeter.

Algorithm

1. Initialize perimeter = 0.
2. For each cell (r, c) where grid[r][c] == 1:
   • Add 4 to perimeter.
   • For each of the 4 neighbors: if the neighbor is in bounds and is also 1, subtract 1.
3. Return perimeter.

Solution

def islandPerimeter(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    perimeter = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                perimeter += 4
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        perimeter -= 1

    return perimeter


print(islandPerimeter([[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]))  # 16
print(islandPerimeter([[1]]))                                         # 4
print(islandPerimeter([[1,0]]))                                       # 4

Complexity

• Time: O(M * N) — visit every cell once
• Space: O(1) — no extra data structures

2. Formula Approach

Intuition

There’s a neat formula: count the total number of land cells (cells) and the total number of shared edges between adjacent land cells (neighbors). Each land cell contributes 4 edges. Each shared edge between two land cells removes 2 perimeter edges (one from each cell). So:

perimeter = cells * 4 - neighbors * 2

You only need to check right and down neighbors to avoid double-counting shared edges.

Algorithm

1. Count cells = number of 1s in the grid.
2. Count neighbors = number of pairs where a 1 is directly to the right or directly below another 1.
3. Return cells * 4 - neighbors * 2.

Solution

def islandPerimeter(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    cells = 0
    neighbors = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                cells += 1
                # Check right neighbor
                if c + 1 < cols and grid[r][c + 1] == 1:
                    neighbors += 1
                # Check bottom neighbor
                if r + 1 < rows and grid[r + 1][c] == 1:
                    neighbors += 1

    return cells * 4 - neighbors * 2


print(islandPerimeter([[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]))  # 16
print(islandPerimeter([[1]]))                                         # 4
print(islandPerimeter([[1,1],[1,1]]))                                 # 8

Complexity

• Time: O(M * N)
• Space: O(1)

Common Pitfalls

Counting neighbors twice. If you check all 4 directions for neighbors and subtract 1 per adjacent land cell, you’re effectively subtracting 2 per shared edge (once from each side) — which is exactly what the formula approach expresses explicitly.

Checking out-of-bounds neighbors. A cell on the grid border has neighbors outside the grid, which count as water. Always bounds-check before checking grid[nr][nc].