1. Island Perimeter (LeetCode)
Model answer
The task
Given a grid of land and water cells, calculate the total length of the land’s outer boundary. Each cell is square, and only sides next to water or outside the grid count.
Key idea
Start with four sides for every land cell. Subtract one for each side shared with another land cell; equivalently, count a side only when its neighbor is water or out of bounds.
Approach
- Record the grid’s row and column counts.
- Visit every cell.
- For each land cell, check its four neighboring positions.
- Add one to the perimeter for each neighbor that is outside the grid or water.
- Return the accumulated perimeter.
from typing import List
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
rows = len(grid)
cols = len(grid[0])
perimeter = 0
# Each exposed side of a land cell contributes one unit.
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
for row in range(rows):
for col in range(cols):
if grid[row][col] == 0:
continue
for dr, dc in directions:
neighbor_row = row + dr
neighbor_col = col + dc
# An out-of-grid or water neighbor leaves this side exposed.
if (
neighbor_row < 0
or neighbor_row >= rows
or neighbor_col < 0
or neighbor_col >= cols
or grid[neighbor_row][neighbor_col] == 0
):
perimeter += 1
return perimeter
Complexity:
- Time: O(RC), where R and C are the grid dimensions; each cell checks four neighbors.
- Space: O(1), excluding the input grid; only a fixed number of variables are used.
Common follow-ups
- Can you use DFS or BFS? Yes; traverse the island and count exposed sides for each visited land cell, though a full grid scan is simpler.
- What if the grid has multiple islands? The same scan returns the sum of their perimeters.
- How would you handle a very large grid that does not fit in memory? Process it in chunks while retaining boundary rows or columns needed to check neighbors.