Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

827. Making A Large Island - Leetcode Solution

Code Implementation

class Solution:
    def largestIsland(self, grid):
        n = len(grid)
        island_id = 2
        area = {}
        
        def dfs(r, c, id):
            if r < 0 or r >= n or c < 0 or c >= n or grid[r][c] != 1:
                return 0
            grid[r][c] = id
            res = 1
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                res += dfs(r+dr, c+dc, id)
            return res
        
        # 1. Label each island with a unique id and compute its area
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    area[island_id] = dfs(r, c, island_id)
                    island_id += 1
        
        res = max(area.values() or [0])
        
        # 2. Try to flip each 0 and sum the areas of neighboring islands
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 0:
                    seen = set()
                    for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                        nr, nc = r+dr, c+dc
                        if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] > 1:
                            seen.add(grid[nr][nc])
                    res = max(res, 1 + sum(area[i] for i in seen))
        return res
      
class Solution {
public:
    int n;
    vector<vector<int>> dirs{{0,1},{0,-1},{1,0},{-1,0}};
    
    int dfs(vector<vector<int>>& grid, int r, int c, int id) {
        if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1) return 0;
        grid[r][c] = id;
        int res = 1;
        for (auto& d : dirs) {
            res += dfs(grid, r + d[0], c + d[1], id);
        }
        return res;
    }
    
    int largestIsland(vector<vector<int>>& grid) {
        n = grid.size();
        unordered_map<int, int> area;
        int island_id = 2;
        
        // 1. Label each island and calculate area
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                if (grid[r][c] == 1) {
                    area[island_id] = dfs(grid, r, c, island_id);
                    ++island_id;
                }
            }
        }
        
        int res = 0;
        for (auto& kv : area) res = max(res, kv.second);
        
        // 2. Try to flip each 0 and sum areas of neighboring islands
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                if (grid[r][c] == 0) {
                    unordered_set<int> seen;
                    int total = 1;
                    for (auto& d : dirs) {
                        int nr = r + d[0], nc = c + d[1];
                        if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] > 1) {
                            seen.insert(grid[nr][nc]);
                        }
                    }
                    for (int id : seen) total += area[id];
                    res = max(res, total);
                }
            }
        }
        return n * n == res ? res : max(res, 1); // handle all 0 grid
    }
};
      
class Solution {
    int n;
    int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
    
    int dfs(int[][] grid, int r, int c, int id) {
        if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1) return 0;
        grid[r][c] = id;
        int res = 1;
        for (int[] d : dirs) {
            res += dfs(grid, r + d[0], c + d[1], id);
        }
        return res;
    }
    
    public int largestIsland(int[][] grid) {
        n = grid.length;
        Map<Integer, Integer> area = new HashMap<>();
        int island_id = 2;
        
        // 1. Label each island and calculate area
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                if (grid[r][c] == 1) {
                    area.put(island_id, dfs(grid, r, c, island_id));
                    ++island_id;
                }
            }
        }
        
        int res = 0;
        for (int v : area.values()) res = Math.max(res, v);
        
        // 2. Try to flip each 0 and sum areas of neighboring islands
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                if (grid[r][c] == 0) {
                    Set<Integer> seen = new HashSet<>();
                    int total = 1;
                    for (int[] d : dirs) {
                        int nr = r + d[0], nc = c + d[1];
                        if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] > 1) {
                            seen.add(grid[nr][nc]);
                        }
                    }
                    for (int id : seen) total += area.get(id);
                    res = Math.max(res, total);
                }
            }
        }
        return n*n == res ? res : Math.max(res, 1);
    }
}
      
var largestIsland = function(grid) {
    const n = grid.length;
    let islandId = 2;
    const area = {};
    
    function dfs(r, c, id) {
        if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] !== 1) return 0;
        grid[r][c] = id;
        let res = 1;
        const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
        for (const [dr, dc] of dirs) {
            res += dfs(r+dr, c+dc, id);
        }
        return res;
    }
    
    // 1. Label each island and calculate area
    for (let r = 0; r < n; ++r) {
        for (let c = 0; c < n; ++c) {
            if (grid[r][c] === 1) {
                area[islandId] = dfs(r, c, islandId);
                ++islandId;
            }
        }
    }
    
    let res = 0;
    for (let key in area) res = Math.max(res, area[key]);
    
    // 2. Try to flip each 0 and sum areas of neighboring islands
    for (let r = 0; r < n; ++r) {
        for (let c = 0; c < n; ++c) {
            if (grid[r][c] === 0) {
                const seen = new Set();
                let total = 1;
                const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
                for (const [dr, dc] of dirs) {
                    const nr = r + dr, nc = c + dc;
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] > 1) {
                        seen.add(grid[nr][nc]);
                    }
                }
                for (let id of seen) total += area[id];
                res = Math.max(res, total);
            }
        }
    }
    return res === 0 ? 1 : res;
};

Problem Description

You are given an n x n binary grid, where each cell contains either 0 (water) or 1 (land). An island is a group of 1s connected horizontally or vertically (not diagonally).

You may change at most one 0 to 1 (i.e., flip a water cell to land). After this change, you want to find the size of the largest possible island in the grid.

  • You can flip at most one 0 to 1.
  • Return the size (number of cells) of the largest possible island after this operation.
  • If the grid is already all land, return n * n.
  • Islands are only connected via their four direct neighbors (up, down, left, right).

Thought Process

At first glance, it might seem like we would need to try flipping every 0 to 1 and, for each, compute the size of the resulting largest island. However, this would be very inefficient for large grids.

Instead, we can break the problem into two main parts:

  • First, identify all existing islands and compute their sizes.
  • Then, for each 0 cell, consider flipping it and calculate the combined area of all distinct neighboring islands that would be connected through this flip.
This approach avoids redundant work and leverages the fact that flipping a 0 can only connect up to four neighboring islands.

The key insight is to uniquely label each island and store its area, so when checking a 0 cell, we can quickly sum the areas of unique adjacent islands.

Solution Approach

  • Step 1: Label Islands and Compute Areas
    • Traverse the grid. For each unvisited 1, perform DFS or BFS to mark all connected 1s with a unique island id (starting from 2 to avoid confusion with 0 and 1).
    • While marking, count the number of cells to determine the area of each island. Store these in a hash map: {island_id: area}.
  • Step 2: Try Flipping Each 0 Cell
    • For each 0 cell, look at its four neighbors. Collect the unique island ids (to avoid double-counting the same island).
    • Sum the areas of these unique neighboring islands and add 1 (for the flipped cell itself).
    • Keep track of the maximum combined area found.
  • Step 3: Edge Cases
    • If the grid is already all land, return n * n.
    • If there are no 1s, flipping any 0 gives an island of size 1.
  • Why This Works
    • Labeling islands allows O(1) area lookups for each flip candidate.
    • By using a set for neighboring ids, we avoid counting the same island multiple times.
    • Each cell is visited a constant number of times, making the solution efficient.

Example Walkthrough

Consider the input grid: 

    1 0
    0 1
  • Step 1: Label islands.
    • Top-left (0,0) is a 1: assign island id 2, area = 1.
    • Bottom-right (1,1) is a 1: assign island id 3, area = 1.
  • Step 2: Try flipping each 0:
    • Cell (0,1) neighbors: (0,0) (island 2), (1,1) (island 3). If we flip (0,1), the connected area is 1 (flipped) + 1 (island 2) + 1 (island 3) = 3.
    • Cell (1,0) also connects both islands; flipping it also yields area 3.
  • Result: The largest possible island size is 3.

Time and Space Complexity

  • Brute-force:
    • For every 0, flip it and run DFS/BFS to find the largest island. This is O(n4), which is too slow for large grids.
  • Optimized Approach:
    • Labeling all islands: O(n2) (each cell visited once).
    • For each 0, checking up to 4 neighbors and summing: O(n2).
    • Total: O(n2) time and O(n2) space for labels and area mapping.

The optimized approach is efficient and suitable for large grids.

Summary

By uniquely labeling each island and storing their areas, we can efficiently determine the effect of flipping any 0 cell. This avoids redundant computation and ensures that each possible flip is considered in constant time relative to the number of neighbors. The solution is both elegant and optimal for the problem constraints.