Island Perimeter

The key idea

Each land cell starts with 4 sides. Every time two land cells sit next to each other, they hide one side from each of them. So the perimeter is 4 * land - 2 * shared_edges, or equivalently you add 4 per land cell and subtract 2 for every adjacent land pair.

Problem

You are given a 2-D grid grid where grid[i][j] == 1 is land and grid[i][j] == 0 is water. Cells connect horizontally and vertically (never diagonally). The whole grid is surrounded by water and holds exactly one island — one or more connected land cells. The island has no inner lakes: there is no water inside it that is cut off from the outside water. Each cell is a square with side length 1. Return the perimeter of the island — the total length of its outer boundary.

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.

Examples

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

Input: grid = [[1]] Output: 4

Input: grid = [[1,0]] Output: 4

Complexity

Time: O(m*n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →