Island Perimeter

Problem

You are given a 2D grid map where 1 represents land and 0 represents water. The grid is surrounded by water on all sides, and there is exactly one island (a group of connected land cells connected horizontally or vertically).

Your task is to calculate and return the perimeter of the island.

Input/Output Format

Input: A 2D integer grid grid where grid[i][j] is either 0 (water) or 1 (land).

Output: An integer representing the total perimeter of the island.

Key Observations

• Each land cell contributes up to 4 edges to the perimeter.
• An edge is part of the perimeter if it borders water (0) or the boundary of the grid.
• Two adjacent land cells share an edge, which removes 2 from the total perimeter count (one from each cell).

Examples

Example 1

Grid:
0 1 0 0
1 1 1 0
0 1 0 0
1 1 0 0

Output: 16

The island has 8 land cells. Each contributes 4 potential edges = 32. Adjacent pairs reduce this. Count shared edges and subtract.

Example 2

Grid:
1

Output: 4

A single land cell has all 4 edges exposed.

Example 3

Grid:
1 1
1 1

Output: 8

A 2×2 island — 4 cells × 4 edges = 16, minus 4 shared interior edges × 2 = 8.

Approach Hints

Approach 1 — Counting Formula:

For each land cell, start with 4. For each neighboring land cell (up/down/left/right), subtract 1. Sum this over all cells.

Approach 2 — BFS/DFS Traversal:

Start from any land cell, traverse the island using BFS or DFS, and accumulate the perimeter contribution of each visited cell by checking its 4 neighbors.

Both approaches run in O(m × n) time where m and n are the grid dimensions.

Notes

• The grid dimensions will always be at least 1×1.
• There is exactly one island in the input.
• Diagonal cells are not considered connected.