201. Island Coastline
A map is a grid where 1 marks a square of land and 0 marks water. Every land square is a unit square, and the whole grid is surrounded by water on all four sides.
The coastline is made of every unit edge that has land on one side and water on the other, where the area outside the grid counts as water. For example, a single land square has a coastline of 4, and two land squares side by side have a coastline of 6, because the edge they share is not on the coast.
Return the total length of the coastline of all land squares in grid.
Example 1
- Input:
- grid = [[0,1,0],[1,1,1],[0,1,0]]
- Output:
- 12
- Explanation:
The plus shape has five land squares with 4 shared edges between them, so the coastline is 5 x 4 - 2 x 4 = 12.
Example 2
- Input:
- grid = [[1]]
- Output:
- 4
- Explanation:
One land square is bordered by water on all four sides.
Example 3
- Input:
- grid = [[1,1,1,1]]
- Output:
- 10
- Explanation:
A row of four squares has 3 shared edges: 4 x 4 - 2 x 3 = 10.
Constraints
1 ≤ grid.length, grid[0].length ≤ 100
grid[i][j] is 0 or 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(m × n)
- Space
- O(1)