Perimeter Of An Island
Problem
A grid holds 1 for land and 0 for water, and all the land forms a single connected island with no lakes inside it. Measure the length of the island's coastline, counting one unit for each cell side that touches water or the edge of the grid.
Examples
Input: grid = [[0, 1, 0, 0],
[1, 1, 1, 0],
[0, 1, 0, 0],
[1, 1, 0, 0]]
Output: 16Input: grid = [[1, 1],
[1, 1]]
Output: 8
Why: a solid square of four cells has eight exposed sidesInput: grid = [[1]]
Output: 4
Why: edge case, a lone cell is exposed on every sideHints
0 / 3
You do not have to walk the coast in order. Every unit of coastline belongs to exactly one land cell, so the cells can be visited in any order at all.
Look at a single land cell and ask which of its four sides face something that is not land.
Sweep the whole grid. For each land cell, check the four neighbouring positions, and add one for each neighbour that is either off the grid or water. The running total is the perimeter.
Solution
Each unit of coastline is one side of one land cell, so the perimeter can be summed cell by cell rather than traced as a loop. A side counts when the neighbour in that direction is water, or when it falls off the grid entirely, which is the same check with the bounds test folded in. That makes the whole thing a plain sweep with four probes per cell and no traversal state. Time is O(rows * cols), and space is O(1).
def perimeter(g):
rows, cols, total = len(g), len(g[0]), 0
for r in range(rows):
for c in range(cols):
if g[r][c] != 1:
continue
for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
off = not (0 <= nr < rows and 0 <= nc < cols)
if off or g[nr][nc] == 0: # that side faces water or the edge
total += 1
return total
print(perimeter([[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0], [1, 1, 0, 0]])) # -> 16
print(perimeter([[1, 1], [1, 1]])) # -> 8
print(perimeter([[1]])) # -> 4Stuck on the idea rather than the code? Grid Traversal covers it.