Island counting, max island area and max island perimeter in Python
Here are three similar algorithms in Python for operations on “island problems”.
These are problems were the input is a 2D matrix of grid coordinates, where 0
represents sea and 1 represents land.
For example:
[
[1, 0, 1, 0, 1],
[1, 0, 1, 0, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 0, 0],
[1, 1, 0, 0, 1],
]
It’s slightly hard to see, but there are 5 islands in this grid: one in each corner, and a larger contiguous one in the shape of an L.
The general approach for these algorithms is similar: iterate the grid, and when we hit a land cell, mark of all of its neighbouring land cells as visited while keeping track of whichever piece of information we’re interested in.
This approach is $O(n)$ for all of these problems, as we visit each cell once or twice.
Each of the solutions needs to import some types, and also a deque for
handling the queue of cells to visit.
We’ll also need a list of directions to check neighbouring cells.
from typing import List, Set, Tuple
from collections import deque
DIRS = [
[-1, 0],
[0, 1],
[1, 0],
[0, -1],
]
Island counting
The island counting algorithm is the simplest, as we don’t need to track anything about each separate island. When we hit a land cell, we mark all of its neighbours as visited, and increment our total island count by one.
This can be done recursively, but I’m using a queue here instead, which I think makes it easier to follow and debug.
def count_islands(grid: List[List[int]]) -> int:
s = len(grid)
island_count = 0
visited = set() # type: Set[Tuple[int, int]]
for i, row in enumerate(grid):
for j, cell in enumerate(row):
if cell == 0 or (i, j) in visited:
continue
island_count += 1
vis_nxt = deque()
vis_nxt.append((i, j))
while vis_nxt:
vis = vis_nxt.popleft()
if vis in visited:
continue
visited.add(vis)
if grid[vis[0]][vis[1]] == 0:
continue
for d in DIRS:
nbr = (vis[0] + d[0], vis[1] + d[1])
if nbr[0] < 0 or nbr[1] < 0 or nbr[0] >= s or nbr[1] >= s:
continue
vis_nxt.append((vis[0] + d[0], vis[1] + d[1]))
return island_count
Max island area
The max island area algorithm is perhaps slightly trickier than the total island count, and slightly less tricky than the max island perimeter algorithm.
The only difference from the total island count algorithm is that we count each neighbouring land cell as we visit a contiguous island, and then track the max of that after each whole island visit.
def max_island_area(grid: List[List[int]]) -> int:
s = len(grid)
mia = 0
visited = set() # type: Set[Tuple[int, int]]
for i, row in enumerate(grid):
for j, cell in enumerate(row):
if (i, j) in visited:
continue
if cell == 0:
continue
tia = 0
nxt_q = deque()
nxt_q.append((i, j))
while nxt_q:
nxt = nxt_q.popleft()
if grid[nxt[0]][nxt[1]] == 0 or nxt in visited:
continue
visited.add(nxt)
tia += 1
for d in DIRS:
nbr = (nxt[0] + d[0], nxt[1] + d[1])
if nbr[0] < 0 or nbr[1] < 0 or nbr[0] >= s or nbr[1] >= s:
continue
nxt_q.append(nbr)
mia = max(mia, tia)
return mia
Max island perimeter
The last of these three problems is tracking the max island perimeter. This is probably a little bit harder than the other two, but not by much.
The main difference is that there’s a little trick to calculating the island perimeter, which is to add 4 for each island cell, and also subtract 2 for each neighbour of a cell to the west or the north. This is because we don’t want to count an internal perimeter, i.e. an edge between two neighbouring land cells. We subtract 2 for each of these because we previously added 4 full edges for both of the neighbouring cells.
This diagram might make this a bit clearer:
┌─┐ │A│ ┌─┼═┤ │B║C│ └─┴─┘
There are 3 land cells labelled A, B and C. While visiting them, we add 4 to the perimeter edge count for each. We have now counted 12 edges.
While visiting cell C, we check its neighbour to the north, and see cell A there. This means there is an internal edge there, marked on the diagram with a double line. This isn’t an external perimeter edge, but has been counted twice (once for A and once for C), so we subtract 2.
Next we check C’s neighbour to the west, and find cell B. Again the internal edge between them has been marked with a double line on the diagram. Because we already counted 4 edges for both B and C, we need to subtract 2 to exclude the internal edge between them.
With this approach, we do $4 + 4 + (4 - 2 - 2) = 8$, which is the correct count of external perimeter edges of the island.
Finally, we just apply that sub-algorithm to each island we encounter in the whole grid, and keep track of the max perimeter to return.
def max_island_perimeter(grid: List[List[int]]) -> int:
s = len(grid)
mip = 0
visited = set() # type: Set[Tuple[int, int]]
for i, row in enumerate(grid):
for j, cell in enumerate(grid):
if cell == 0 or (i, j) in visited:
continue
tip = 0
nxt_q = deque()
nxt_q.append((i, j))
while nxt_q:
tc = nxt_q.popleft()
if grid[tc[0]][tc[1]] == 0 or tc in visited:
continue
visited.add(tc)
tip += 4
if tc[0] > 0 and grid[tc[0] - 1][tc[1]] == 1:
tip -= 2
if tc[1] > 0 and grid[tc[0]][tc[1] - 1] == 1:
tip -= 2
for d in DIRS:
nbr = (tc[0] + d[0], tc[1] + d[1])
if nbr[0] < 0 or nbr[1] < 0 or nbr[0] >= s or nbr[1] >= s:
continue
nxt_q.append(nbr)
mip = max(mip, tip)
return mip