Island Perimeter

How it works

Every land cell contributes 4 to the perimeter initially. However, when two land cells are adjacent, they share an edge, and both cells lose one perimeter unit on that shared side. So for each adjacent pair, we subtract 2 from the total. By only checking the top and left neighbors while iterating, we count each adjacency exactly once.

Steps

1. Initialize perimeter to 0.
2. Iterate through every cell in the grid.
3. For each land cell:
   • Add 4 to the perimeter.
   • If the cell above is also land, subtract 2.
   • If the cell to the left is also land, subtract 2.
4. Return the total perimeter.

Complexity

• Time complexity: O(m * n)
• Space complexity: O(1) extra space.

Where m is the number of rows and n is the number of columns in the grid.

Things to watch for

Double Counting Shared Edges

When two adjacent land cells share an edge, that edge should not contribute to the perimeter. A common mistake is to count all 4 sides for every land cell without subtracting the shared edges. Each adjacency between two land cells removes 2 from the total perimeter (1 from each cell).

Forgetting Boundary Conditions

Edges at the grid boundary always contribute to the perimeter. When checking neighbors, failing to properly handle out-of-bounds indices can cause missed perimeter edges or array index errors. Always verify that neighbor coordinates are within valid grid bounds before accessing them.

from typing import List

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        res = 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    res += 4
                    if r and grid[r - 1][c]:
                        res -= 2
                    if c and grid[r][c - 1] == 1:
                        res -= 2
        return res

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int res = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c]) {
                    res += 4;
                    if (r && grid[r - 1][c]) {
                        res -= 2;
                    }
                    if (c && grid[r][c - 1]) {
                        res -= 2;
                    }
                }
            }
        }
        return res;
    }
};