Island Perimeter
Easy · Matrix · Array · Matrix · Depth-First Search · Breadth-First Search
Problem
You are given a rows x cols grid where grid[i][j] == 1 is land and 0 is water. Cells connect only up, down, left and right. The grid holds exactly one island (one connected group of land cells), the island has no lakes (no water enclosed by land), and everything outside the grid is water.
Every cell is a square of side 1. Return the perimeter of the island.
Examples
Input: grid = [[0,1,1],[0,1,0]] Output: 8
Three land cells have 12 sides. Two pairs of cells share a side, and each shared side hides two edges: 12 - 4 = 8.
Input: grid = [[1],[1],[1]] Output: 8
A bar of three cells: two long sides of length 3 and two ends of length 1.
Input: grid = [[1,1],[1,1]] Output: 8
A 2 x 2 square has perimeter 8; the four inner borders do not count.
Constraints
- rows == len(grid), cols == len(grid[i])
- 1 <= rows, cols <= 100
- grid[i][j] is 0 or 1
- There is exactly one island, with no lakes.
Approaches
- Walk the island, count sides facing water — time O(rows · cols), space O(rows · cols) for the visited set and stack
Follow-up
What if the grid could hold lakes, and the shore of a lake should not count? Then you need to know which water is open sea: flood it from the border first, and count only land edges facing sea or the outside. The use case "Coastline that faces the open sea" does exactly that.
Related problems
Start free on Cariara · Coding problems · System design studio
