827. Making A Large Island

• categories: Code, Interview Question, leetcode, Hard
• source: https://leetcode.com/problems/making-a-large-island
• topics: Graph, DFS

Description

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

Idea

1. Find and label islands using DFS, calculating their sizes and marking border cells adjacent to water
2. Store border cell contributions: Each 0 cell is mapped to the islands it connects to
3. If the grid is fully land, return its total size. If no islands exist, return 1 (by flipping any 0)
4. Simulate flipping a 0: The new island area is 1 + sum(connected island sizes)
5. Return the maximum possible island size

Code

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        visited = [[False] * cols for _ in range(rows)]
 
        def dfs(x: int, y: int, border_cells: set) -> int:
            visited[x][y] = True
            area = 1
 
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and not visited[nx][ny]:
                    if grid[nx][ny] == 0:
                        border_cells.add((nx, ny)) 
                    else:
                        area += dfs(nx, ny, border_cells)
 
            return area
 
        # Dictionary to store possible expansions for each border cell
        border_areas = defaultdict(list)
 
        # Step 1: Identify islands and associate their areas with border cells
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1 and not visited[i][j]:
                    border_cells = set()
                    island_area = dfs(i, j, border_cells)
 
                    # If the entire grid is one big island, return its area
                    if not border_cells:
                        return island_area
 
                    # Store island areas mapped to border cells
                    for cell in border_cells:
                        border_areas[cell].append(island_area)
 
        # No islands exist, flipping any '0' creates an island of size 1
        if not border_areas: 
            return 1 if rows and cols else 0
 
        # For every flipped border cell the area will be 1 + sum of connected islands
        return max(1 + sum(areas) for areas in border_areas.values())