Editorial: Island Area and Water Boundary

Overview

At its core, this problem asks us to find all the connected components (islands) of 1s in a grid, and for each component, calculate two metrics: its area, and the number of distinct adjacent 0s (water).

This is a classic graph traversal problem. We can think of the grid as a graph where each cell is a node, and edges connect horizontally and vertically adjacent cells. To solve the problem, we can iterate over every cell in the grid. Whenever we encounter an unvisited land cell (1), we initiate a Depth-First Search (DFS) or Breadth-First Search (BFS) to explore the entire island.

During the traversal:

1. Every time we process a land cell, we increment our area counter.
2. For every land cell, we examine its 4 neighbors. If a neighbor is water (0), we record its coordinates. Using a set to store these coordinates automatically handles deduplication, ensuring we only count distinct water boundaries.

Brute Force

The most straightforward way to implement this is using an explicit stack for an iterative DFS, alongside a visited set to keep track of the land cells we have already processed. This prevents infinite loops and ensures we don't count the same land cell multiple times.

For the water boundary count, we maintain a separate water_cells set for each island. As we traverse the land, any out-of-bounds neighbors are ignored, while valid 0 cells are added to the water_cells set. Once the DFS completes, the size of the water_cells set gives us the unique boundary count.

def island_characteristics(grid: list[list[int]]) -> list[list[int]]:
    m = len(grid)
    n = len(grid[0])
    visited = set()
    result = []
    
    for r in range(m):
        for c in range(n):
            # When we find an unvisited piece of land, explore the whole island
            if grid[r][c] == 1 and (r, c) not in visited:
                area = 0
                water_cells = set()
                
                # Start DFS
                stack = [(r, c)]
                visited.add((r, c))
                
                while stack:
                    curr_r, curr_c = stack.pop()
                    area += 1
                    
                    # Check all 4 directional neighbors
                    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                        nr, nc = curr_r + dr, curr_c + dc
                        
                        # Ensure the neighbor is within grid boundaries
                        if 0 <= nr < m and 0 <= nc < n:
                            if grid[nr][nc] == 1 and (nr, nc) not in visited:
                                visited.add((nr, nc))
                                stack.append((nr, nc))
                            elif grid[nr][nc] == 0:
                                water_cells.add((nr, nc))
                                
                result.append([area, len(water_cells)])
                
    return result

• Time complexity: O(m * n) — We visit every cell in the grid a constant number of times (once in the main loop, and at most 4 times when checked as a neighbor).
• Space complexity: O(m * n) — In the worst-case scenario (a grid entirely filled with land), the visited set and the DFS stack will store all cells.

Optimal / Best Approach

We can optimize the space complexity by eliminating the visited set for land cells. Instead of tracking visited land in a separate data structure, we can modify the grid in-place.

When we visit a 1, we can change it to a -1 (or any value other than 0 and 1). This acts as an embedded visited marker. We must be careful not to change it to 0, as that would trick subsequent checks on the same island into counting it as a water boundary!

Using a BFS via collections.deque provides an optimal, level-by-level traversal.

from collections import deque

def island_characteristics(grid: list[list[int]]) -> list[list[int]]:
    m = len(grid)
    n = len(grid[0])
    result = []
    
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 1:
                area = 0
                water_cells = set()
                
                # Start BFS
                queue = deque([(r, c)])
                grid[r][c] = -1  # Mark as visited immediately to avoid duplicate queueing
                
                while queue:
                    curr_r, curr_c = queue.popleft()
                    area += 1
                    
                    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                        nr, nc = curr_r + dr, curr_c + dc
                        
                        if 0 <= nr < m and 0 <= nc < n:
                            if grid[nr][nc] == 1:
                                grid[nr][nc] = -1  # Mark visited
                                queue.append((nr, nc))
                            elif grid[nr][nc] == 0:
                                water_cells.add((nr, nc))
                                
                result.append([area, len(water_cells)])
                
    return result

• Time complexity: O(m * n) — Every cell is processed at most a constant number of times.
• Space complexity: O(m * n) — Though we save space by removing the visited set, the worst-case space bound remains $O(m \times n)$ because the water_cells set and the queue could still scale proportionally with the grid size (e.g., in a checkerboard pattern grid).

Edge Cases

• No islands: If the grid is composed entirely of 0s, the loops will simply finish without initiating any BFS, and the function will correctly return an empty list [].
• One giant island: If the grid is entirely 1s, a single BFS will traverse the whole grid. The water_cells set will be empty, and the function will return [[m * n, 0]].
• Checkerboard pattern: A grid alternating between 1s and 0s maximizes the number of distinct islands and forces the algorithm to handle many small traversals efficiently. The logic remains robust and bounded within our constraints.