Coastline Length
EasyGraphs
Problem
A coastal authority needs to know how much fence it must buy. The map grid uses 1 for land and 0 for water; every cell is a 1 × 1 square, and everything outside the grid is water.
Fence goes on every unit edge that separates a land cell from water (including water outside the map and lakes inside an island). Return the total length of fence needed across all land.
Example 1
- Input:
- grid = [[0,1,0],[1,1,1],[0,1,0]]
- Output:
- 12
The plus shape has 5 cells, i.e. 20 edges, and 4 shared edges between land cells remove 2 × 4 = 8 of them.
Example 2
- Input:
- grid = [[1,1],[1,1]]
- Output:
- 8
Constraints
- 1 ≤ rows, cols ≤ 100
- grid[r][c] is 0 or 1
- The grid may contain several islands and lakes.
Hint
Show the first hint
Each land cell has four edges. Which of them need fence?
Walkthrough
How to approach it
01Clarify before coding
- Do lake shores count? Yes: any land edge facing water, inside or outside, needs fence.
- Can there be several islands? Yes, the answer sums them all.
- Is the outside of the grid water? Yes.
02Brute force
Flood-fill each island and, for every visited cell, check its four neighbours, counting those that are water or off the grid.
Cost: O(r · c) time but O(r · c) extra space for the traversal, and a lot of machinery for a local property.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.