Island areas and water boundaries

Question: Island areas and water boundaries

Companies: Waymo

Difficulty: Medium

Problem statement

You are given an m x n grid of characters. Each cell is '1' (land) or '0' (water). Land cells that share a side (up, down, left or right) belong to the same island. Diagonal cells are not connected.

For every island, report two numbers:

• Area: how many land cells the island has.
• Water boundary: how many cell sides of the island touch water. Treat everything outside the grid as water, so a land side on the edge of the map counts. A side shared by two land cells of the island does not count.

Implement island_stats(grid) -> list[tuple[int, int]], returning one (area, boundary) pair per island. List islands in the order a row-by-row, left-to-right scan first reaches them. The number of islands is the length of the result.

Constraints

• 0 <= m, n <= 1000
• Each cell is '0' or '1'.
• Aim for O(m * n) time. Your solution must not fail on a grid that is entirely land.

Example 1

grid = ["1100",
        "1001",
        "0011"]

Output: [(3, 8), (3, 8)]. The top-left island has 3 cells and 8 sides that face water or the map edge. The bottom-right island also has 3 cells and 8 such sides.

Example 2

grid = ["111",
        "101",
        "111"]

Output: [(8, 16)]. The ring has 12 sides on the outside and 4 sides around the water cell in the middle.

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

Approach

Clarify first. The grid holds '0' (water) and '1' (land), connected only up, down, left and right. For each island we report its area (land cells) and its water boundary: the number of cell edges where the island touches water. Ask whether the grid edge counts as water. The usual answer, and the one used here, is yes: the map is surrounded by sea. Also ask about the output order. Here islands come out in the row-major order of their first cell, which is the order a scan finds them. Ask whether you may modify the input. This solution does not; it keeps a seen matrix.

Start from Number of Islands. Scan every cell. When you hit unvisited land, flood-fill the island and count it. That gives the island count in O(m * n). The two new numbers fall out of the same flood fill, so there is no need for a second pass.

Area. Every cell the flood fill pops belongs to the island and is popped exactly once, so the area is the number of pops.

Water boundary. A land cell has four sides. A side is boundary when the neighbor across it is out of bounds or water. Inside the flood fill we already look at all four neighbors, so add one to the boundary for each neighbor that is not land. A side shared by two land cells is never counted, because neither cell sees water there.

An equivalent formula is boundary = 4 * area - 2 * shared_edges, where shared_edges counts land-land adjacencies inside the island. It is a nice check, and it lets a second-pass solution compute boundary without a flood fill.

Why BFS with an explicit queue. A recursive DFS on a 1000 x 1000 all-land grid recurses a million levels and crashes Python. An iterative BFS (or a stack-based DFS) has no depth limit. Mark a cell as seen when you push it, not when you pop it, so no cell enters the queue twice.

Invariants.

• Every land cell is in exactly one island, and it is popped exactly once.
• Each of a land cell's four sides is counted as boundary at most once, and only when the other side is not land.
• The sum of all areas equals the number of '1' cells.

Code

from collections import deque
from typing import NamedTuple

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


class Island(NamedTuple):
    area: int
    boundary: int


def island_stats(grid: list[list[str]]) -> list[Island]:
    """Area and water boundary of each island, in row-major order of discovery.

    The edge of the grid counts as water.
    """
    if not grid or not grid[0]:
        return []
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    islands: list[Island] = []

    def is_land(r: int, c: int) -> bool:
        return 0 <= r < rows and 0 <= c < cols and grid[r][c] == "1"

    for r0 in range(rows):
        for c0 in range(cols):
            if grid[r0][c0] != "1" or seen[r0][c0]:
                continue
            area = boundary = 0
            seen[r0][c0] = True
            queue: deque[tuple[int, int]] = deque([(r0, c0)])
            while queue:
                r, c = queue.popleft()
                area += 1
                for dr, dc in DIRS:
                    nr, nc = r + dr, c + dc
                    if not is_land(nr, nc):
                        boundary += 1          # side faces water or the map edge
                    elif not seen[nr][nc]:
                        seen[nr][nc] = True    # mark on push: no duplicates
                        queue.append((nr, nc))
            islands.append(Island(area, boundary))
    return islands


def count_islands(grid: list[list[str]]) -> int:
    return len(island_stats(grid))


def parse(rows: list[str]) -> list[list[str]]:
    return [list(row) for row in rows]


if __name__ == "__main__":
    g = parse(["1100",
               "1001",
               "0011"])
    assert island_stats(g) == [Island(3, 8), Island(3, 8)]
    assert count_islands(g) == 2

    assert island_stats(parse(["1"])) == [Island(1, 4)]
    assert island_stats(parse(["000"])) == []
    assert island_stats([]) == []
    assert island_stats(parse(["111", "111"])) == [Island(6, 10)]
    # Ring: inner lake sides count as water boundary too.
    assert island_stats(parse(["111", "101", "111"])) == [Island(8, 16)]
    # Diagonal cells are separate islands.
    assert island_stats(parse(["10", "01"])) == [Island(1, 4), Island(1, 4)]
    # Single row strip.
    assert island_stats(parse(["11011"])) == [Island(2, 6), Island(2, 6)]
    # Big all-land grid: no recursion limit problems.
    n = 600
    big = [["1"] * n for _ in range(n)]
    assert island_stats(big) == [Island(n * n, 4 * n)]
    print("ok")

Complexity

• Time: O(m * n). Each cell is scanned once by the outer loop, and each land cell is pushed and popped once, with four neighbor checks.
• Space: O(m * n) for the seen matrix. The BFS queue holds at most O(min(m, n)) cells on a frontier in typical shapes and O(m * n) in the worst case. If mutating the input is allowed, overwrite visited land with '0' and drop seen; the queue is then the only extra space.
• Output: O(k) for k islands.

Test cases

• ["1100", "1001", "0011"] -> [(3, 8), (3, 8)]. The L-shape at the top left has 3 cells and 8 water sides; the other island has 3 cells and 8.
• ["1"] -> [(1, 4)]. A lone cell has all four sides on the map edge.
• ["000"] -> []. No land.
• [] -> []. Empty grid.
• ["111", "111"] -> [(6, 10)]. A full 2 x 3 rectangle has perimeter 2 * (2 + 3).
• ["111", "101", "111"] -> [(8, 16)]. A ring: 12 outer sides plus 4 sides facing the inner lake.
• ["10", "01"] -> [(1, 4), (1, 4)]. Diagonal cells are not connected.
• ["11011"] -> [(2, 6), (2, 6)].
• A 600 x 600 grid of all land -> [(360000, 2400)]. Checks that the traversal has no recursion depth problem.

Follow-ups

1. Only the boundary that touches real water. If the grid edge does not count as water, change the boundary test to count only in-bounds '0' neighbors. Everything else is the same.
2. Separate the sea from lakes. Count only sides that touch ocean water, meaning water connected to the grid edge. First flood-fill the water from every border water cell and mark it as ocean. Then a side counts only when the neighbor is ocean or out of bounds. The ring example drops from 16 to 12. Still O(m * n).
3. Count water cells, not sides. Some interviewers mean "how many distinct water cells touch this island". Collect neighbor water cells into a per-island set (or stamp them with the island id in an int matrix so you never count a cell twice for the same island). One water cell can touch several islands and counts once for each.
4. Largest island, or top k. Keep the stats and take max by area, or a heap of size k. Ties can be broken by boundary (a compact island has a smaller boundary for the same area).
5. Streaming land additions (Number of Islands II). Cells turn to land one at a time and you report the stats after each. Use union-find keyed by cell. Each root stores area and boundary. A new cell starts with area 1 and boundary 4. For each land neighbor, subtract 2 from the boundary (the shared side disappears from both cells) and union, adding the areas and boundaries. Each addition is near O(1) amortized.

Interviewer expectations

Mid-level (L4)

• Solves Number of Islands quickly and extends the same traversal to area and boundary.
• Gets the boundary rule right, including the grid edge, and does not double count shared sides.
• Tests a single cell, an empty grid and diagonal cells.

Senior (L5)

• Asks whether the grid edge counts as water and whether the input may be mutated, before coding.
• Uses an iterative traversal and explains why recursion fails on a large all-land grid.
• Gives the 4 * area - 2 * shared_edges check and handles the lake-versus-ocean follow-up cleanly.

Staff (L6+)

• Moves to union-find for streaming updates and keeps area and boundary correct during unions.
• Discusses very large maps: processing row bands with a union-find that merges across band seams, or tiling the map across workers.
• Relates the problem to real map data, such as connected regions in an occupancy grid, and what changes with 8-connectivity or noisy cells.