Largest island perimeter in a grid: Frontier Interview's solution

Question: Largest island perimeter in a grid

Companies: Google, Tesla

Difficulty: Medium

Problem statement

You are given an m x n grid where each cell is either land ("1") or water ("0"). Land cells that touch horizontally or vertically (not diagonally) belong to the same island.

Treat every land cell as a unit square with four sides. A side is part of its island's perimeter when the cell on the other side is water or lies outside the grid. Water enclosed by an island counts as water, so its edges are part of the perimeter too.

Implement:

def max_island_perimeter(grid: list[list[str]]) -> int: ...

Return the largest perimeter of any island in the grid, or 0 if there is no land. The island with the most cells does not always have the largest perimeter.

Constraints

0 <= m, n <= 1000
grid[i][j] is "0" or "1"
Your solution should run in time linear in the number of cells and must not depend on deep recursion.

Example 1

grid = [
  ["1","1","0","0"],
  ["1","1","0","1"],
  ["0","0","0","1"],
  ["1","1","1","1"],
]

Output: 14. The top-left 2x2 block has perimeter 8. The six cells on the right and bottom form one L-shaped island with perimeter 14.

Example 2

grid = [
  ["1","1","1"],
  ["1","0","1"],
  ["1","1","1"],
]

Output: 16. The ring has 12 outer edges plus 4 edges facing the enclosed water.

Be ready to extend your solution, for example to land that is added one cell at a time.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

This is Number of Islands with a score attached to each island. Find every
connected group of land cells, compute that group's perimeter, and keep the
largest.

Counting one island's perimeter. Each land cell owns four unit edges. An
edge is on the perimeter unless the cell on the other side is land. So for one
island:

perimeter = sum over its cells of (4 - number of land neighbours)
          = 4 * cells - 2 * (shared edges inside the island)

You do not need to look at water cells or treat the grid border specially:
"neighbour is out of bounds" and "neighbour is water" both count as an exposed
edge. A water pocket enclosed by the island (a lake) also counts, because its
edges touch water. If the interviewer wants only the outer coastline, see the
follow-ups.

Brute force. For each land cell, flood-fill its island from scratch and
sum the exposed edges. That repeats the same island once per cell, which is
O((mn)^2) in the worst case. Nobody should stop here, but saying it shows why
you need a visited set.

Optimal. Scan the grid once. When you reach an unvisited land cell, run an
iterative BFS (or DFS with an explicit stack) from it. While you pop each
cell, add 4 - land_neighbours to a running total for that island, and push
unvisited land neighbours. When the queue empties, compare the total with the
best so far. Every cell is visited once and checks four neighbours, so the
whole scan is linear.

Invariants:

A cell is marked visited at the moment it is pushed, so no cell is enqueued
twice and no island is counted twice.
An island's total depends only on its own cells. A land neighbour is always
in the same island, so counting it as "not exposed" never leaks across
islands.
Use an explicit queue, not recursion. A 1000 x 1000 grid of all land would
overflow Python's recursion limit.

The input is not modified. Mutating the grid to mark visits is fine if the
interviewer allows it, and it saves the O(mn) visited set.

Code

import heapq
from collections import deque
from typing import List, Tuple

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def max_island_perimeter(grid: List[List[str]]) -> int:
    """Largest perimeter of any 4-connected island of '1' cells. 0 if none."""
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    best = 0

    for sr in range(rows):
        for sc in range(cols):
            if grid[sr][sc] != "1" or seen[sr][sc]:
                continue
            seen[sr][sc] = True
            queue = deque([(sr, sc)])
            perimeter = 0
            while queue:
                r, c = queue.popleft()
                perimeter += 4
                for dr, dc in DIRS:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "1":
                        perimeter -= 1  # shared edge, not exposed
                        if not seen[nr][nc]:
                            seen[nr][nc] = True
                            queue.append((nr, nc))
            best = max(best, perimeter)
    return best


class IslandPerimeters:
    """Follow-up: land is added one cell at a time; report the max after each add.

    Union-find keeps a perimeter per root. A new cell with k land neighbours
    adds 4 - 2k to the merged island (its own 4 edges, minus k of them, minus
    the k edges each neighbour loses). That can be negative, e.g. filling a
    lake, so the max is not monotone: keep a max-heap with lazy deletion.
    """

    def __init__(self, rows: int, cols: int) -> None:
        self.rows, self.cols = rows, cols
        self.parent: List[int] = [-1] * (rows * cols)  # -1 means water
        self.perim: List[int] = [0] * (rows * cols)
        self.heap: List[Tuple[int, int]] = []  # (-perimeter, root)

    def _find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def _best(self) -> int:
        while self.heap:
            neg, root = self.heap[0]
            if self.parent[root] == root and self.perim[root] == -neg:
                return -neg
            heapq.heappop(self.heap)  # stale: merged away or value changed
        return 0

    def add_land(self, r: int, c: int) -> int:
        idx = r * self.cols + c
        if self.parent[idx] != -1:
            return self._best()  # already land
        self.parent[idx] = idx
        roots = set()
        land_neighbours = 0
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < self.rows and 0 <= nc < self.cols:
                nidx = nr * self.cols + nc
                if self.parent[nidx] != -1:
                    land_neighbours += 1
                    roots.add(self._find(nidx))
        total = 4 - 2 * land_neighbours + sum(self.perim[root] for root in roots)
        for root in roots:
            self.parent[root] = idx
        self.perim[idx] = total
        heapq.heappush(self.heap, (-total, idx))
        return self._best()

Complexity

max_island_perimeter: O(m·n) time. Each cell is pushed at most once and
checks four neighbours. O(m·n) space for seen and the queue in the worst
case (one island covering the grid). O(1) extra besides the queue if you may
overwrite the grid.
IslandPerimeters.add_land: O(log(m·n)) amortised per call. The
union-find part is near O(1) with path halving (add union by size to make
it strict); each call pushes one heap entry, and each entry is popped at
most once. O(m·n) space.
The answer is not monotone even with additions only: a cell with three or
four land neighbours shrinks its island's perimeter (filling a lake does
this). That is why the follow-up uses a heap instead of a running maximum.

Test cases

[] or [[]] → 0 (empty grid).
[["0","0"],["0","0"]] → 0 (no land).
[["1"]] → 4 (single cell; all four edges on the border).
[["1","1"],["1","1"]] → 8 (2x2 block: 16 - 2·4 shared edges).
[["1","0","1","1"]] → 6 (islands of size 1 and 2; perimeters 4 and 6).
[["1","1","0","0"],["1","0","0","1"],["0","0","1","1"]] → 8 (two
L-shaped islands of three cells, each perimeter 8).
[["1","1","1"],["1","0","1"],["1","1","1"]] → 16 (ring around a lake:
12 outer edges plus 4 lake edges).
A larger island with a smaller perimeter loses: [["1","1","0","1","0","1"],["1","1","0","1","1","1"]]
→ 12 (the 2x2 block has perimeter 8; the 5-cell U shape has 12).
Diagonal cells are separate islands: [["1","0"],["0","1"]] → 4.
1000 x 1000 all "1" → 4000, and it must not hit a recursion limit.
IslandPerimeters(2, 2): add_land(0,0) → 4, add_land(1,1) → 4,
add_land(0,1) → 8 (three cells in an L), add_land(1,0) → 8 (2x2 block).
IslandPerimeters(3, 3): add the eight ring cells → 16, then
add_land(1,1) → 12 (filling the lake shrinks the maximum).

Follow-ups

Return which island it is. Track the start cell (or the list of cells)
of the best island. Break ties with a stated rule, such as the first island
in row-major order. Cost stays linear.
Outer coastline only (ignore lakes). Flood-fill water from every border
water cell first and mark it "ocean". Then count an edge as perimeter only
when it touches the grid border or ocean water. Enclosed water becomes part
of the island for this purpose. Still O(m·n).
Land arrives one cell at a time (Number of Islands II style). Use the
IslandPerimeters union-find above: a new cell with k land neighbours adds
4 - 2k to the merged root's perimeter. Because that change can be
negative, a running maximum is wrong; keep (perimeter, root) pairs in a
max-heap and discard stale tops. If cells can also be removed, union-find
no longer works directly: process the timeline backwards when it is known
offline (removals become additions), or recompute the affected island
with BFS.
Grid too large for memory / streamed row by row. Keep only the previous
row's labels. Run union-find over row segments, carrying each component's
partial perimeter. When a component has no cells in the current row, it is
finished, so compare it with the best and drop it. Memory is O(n).
Different connectivity or shapes. With 8-connectivity, islands merge
across diagonals but the perimeter still counts only the four sides of each
cell, so the per-cell rule is unchanged. On a hex grid each cell has six
sides: use 6 - land_neighbours.

Interviewer expectations

Mid-level (L4)

Recognises the Number of Islands pattern and writes a correct flood fill
with a visited set.
Derives the per-cell rule (4 minus land neighbours) without special-casing
the border by hand.
States O(m·n) time and space and tests the single cell and no-land cases.

Senior (L5)

Uses an iterative traversal and explains the recursion-depth risk on a large
all-land grid.
Raises the lake question before coding and handles the outer-only variant
with an ocean flood fill.
Talks through the incremental version with union-find and the 4 - 2k
update, notices it can be negative, and explains why removals are harder.

Staff (L6+)

Covers grids that do not fit in memory: row streaming with a rolling label
row, or tiling with components merged across tile seams.
Discusses parallelism (per-tile labelling, then a merge pass over the edges)
and the trade-off between mutating the input and using extra memory.
Defines tie-breaks and output contracts clearly, and connects the task to
real uses such as map shoreline or connected-component analysis on images.