30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 827. Making A Large Island

Given an n×n binary grid where you can flip at most one 0 to 1, compute the largest possible 4-directional island size after the flip. Key idea: label connected components and their sizes, then for each 0 consider merging distinct neighboring islands (sum their sizes +1), with the all-ones grid as an edge case.

Asked at:

Meta

DESCRIPTION

Input:


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

Output:

Explanation: Flip the 0 at position (0,1) or (1,0) to connect both islands. Result: one island of size 3

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] is either 0 or 1

Understanding the Problem

Let's understand what we're being asked to do. We have an n×n binary grid where each cell is either 0 (water) or 1 (land). An island is a group of 1s connected horizontally or vertically (4-directional).

For example, in the grid [[1,0],[0,1]], there are two separate islands (top-left and bottom-right), each of size 1. In [[1,1],[1,0]], there's one island of size 3 (the three connected 1s).

The twist: We can flip at most one 0 to 1. Our goal is to find the largest possible island size after this optional flip.

Key constraint: The grid is n×n (square), and 1 <= n <= 500.

Edge cases to consider: What if the grid is already all 1s? (can't flip anything, return n*n). What if flipping a 0 connects multiple separate islands? What if the grid is all 0s? (flip one 0 to get island of size 1).

Brute Force Approach

For each 0 cell in the grid, temporarily flip it to 1, then run a DFS/BFS to compute the size of the resulting island at that position. Track the maximum island size found across all flips. This approach is straightforward but inefficient because we recompute island sizes from scratch for every single 0 cell, leading to repeated work.

def largest_island_brute_force(grid):
    """
    Brute force: For each 0, flip it to 1 and compute island size via DFS.
    Track the maximum island size found across all flips.
    """
    if not grid or not grid[0]:
        return 0
    
    n = len(grid)
    max_island_size = 0
    
    def dfs(r, c, visited):
        # DFS to compute island size starting from (r, c)
        if r < 0 or r >= n or c < 0 or c >= n:
            return 0
        if grid[r][c] == 0 or (r, c) in visited:
            return 0
        
        visited.add((r, c))
        size = 1
        
        # Explore all 4 directions
        size += dfs(r + 1, c, visited)
        size += dfs(r, c + 1, visited)
        size += dfs(r - 1, c, visited)
        size += dfs(r, c - 1, visited)
        
        return size
    
    # Check if grid is already all ones (edge case)
    has_zero = False
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                has_zero = True
                break
        if has_zero:
            break
    
    if not has_zero:
        # All ones - return total grid size
        return n * n
    
    # Try flipping each 0 to 1 and compute resulting island size
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                # Temporarily flip this 0 to 1
                grid[i][j] = 1
                
                # Compute island size at this position using DFS
                visited = set()
                island_size = dfs(i, j, visited)
                
                # Track maximum island size
                max_island_size = max(max_island_size, island_size)
                
                # Flip back to 0 for next iteration
                grid[i][j] = 0
    
    return max_island_size

Start brute force: try flipping each 0 to 1

0 / 106

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n^4) For each of O(n^2) cells, we potentially run DFS that visits O(n^2) cells, resulting in O(n^4) time

Space Complexity: O(n^2) DFS recursion stack can go O(n^2) deep in worst case, plus visited array of size O(n^2)

Building Intuition

When we flip a 0 to 1, we're potentially merging multiple existing islands that are adjacent to that 0.

For example, if a 0 is surrounded by three different islands, flipping it would connect all three into one giant island. The key insight is: we need to know the size of each existing island and which islands are neighbors of each 0.

If we can label each island with a unique ID and store its size, then for any 0 cell, we can look at its 4 neighbors, identify which distinct islands touch it, and calculate: 1 + sum of sizes of distinct neighboring islands.

This transforms the problem from 'try flipping every 0 and recompute' (expensive!) to 'precompute island info once, then check each 0 in constant time' (efficient!).

Imagine coloring each island a different color (red, blue, green, etc.) and writing its size on each cell.

Now when you look at a water cell (0), you can see which colored islands touch it. If it touches red (size 5), blue (size 3), and green (size 2), flipping this water cell would create an island of size 1 + 5 + 3 + 2 = 11.

The 'coloring' step is about identifying connected components, and the 'checking water cells' step is about merging distinct neighbors.

Common Mistakes

Forgetting to use a set when checking neighbors of a 0 cell - this causes double-counting when the same island touches from multiple directions

Not handling the all-1 grid edge case - the answer should be n*n, not n*n + 1 (we can't flip anything)

Off-by-one errors in boundary checks when examining 4-directional neighbors - always verify 0 <= row < n and 0 <= col < n

Starting island IDs at 0 or 1 - this conflicts with the grid values! Use IDs starting at 2 or use negative numbers to avoid confusion

Forgetting to reset visited state between DFS calls during the labeling phase - each island needs its own DFS traversal

Optimal Solution

First, label each connected component (island) with a unique ID and compute its size using DFS. Store this information in a map. Then, for each 0 cell, examine its 4 neighbors to identify which distinct islands touch it (using a set to avoid counting the same island multiple times). The potential island size from flipping this 0 is 1 + sum of distinct neighboring island sizes. Track the maximum across all 0 cells, and handle the edge case where the grid is already all 1s.

def largest_island(grid):
    """
    Find the largest island after flipping at most one 0 to 1.
    Uses DFS to label components, then checks each 0 for merge potential.
    """
    if not grid or not grid[0]:
        return 0
    
    n = len(grid)
    island_id = 2  # Start from 2 (0 and 1 are already used)
    island_sizes = {}  # Map island_id -> size
    
    def dfs(r, c, island_id):
        """Label connected 1s with island_id and return size."""
        if r < 0 or r >= n or c < 0 or c >= n:
            return 0
        if grid[r][c] != 1:
            return 0
        
        grid[r][c] = island_id
        size = 1
        
        # Explore all 4 directions
        size += dfs(r + 1, c, island_id)
        size += dfs(r - 1, c, island_id)
        size += dfs(r, c + 1, island_id)
        size += dfs(r, c - 1, island_id)
        
        return size
    
    # Phase 1: Label all islands and compute their sizes
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                size = dfs(i, j, island_id)
                island_sizes[island_id] = size
                island_id += 1
    
    # Edge case: grid is all 1s
    if not island_sizes:
        return 0
    if len(island_sizes) == 1 and sum(island_sizes.values()) == n * n:
        return n * n
    
    max_size = max(island_sizes.values()) if island_sizes else 0
    
    # Phase 2: Check each 0 for potential merge
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 0:
                # Find distinct neighboring islands
                neighbor_islands = set()
                
                for dr, dc in directions:
                    ni, nj = i + dr, j + dc
                    if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] > 1:
                        neighbor_islands.add(grid[ni][nj])
                
                # Calculate potential size: 1 (flipped cell) + sum of neighbor island sizes
                potential_size = 1
                for island in neighbor_islands:
                    potential_size += island_sizes[island]
                
                max_size = max(max_size, potential_size)
    
    return max_size

Start: Find largest island after flipping at most one 0 to 1

0 / 70

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n^2) We visit each cell once during DFS labeling (O(n^2)), then check each cell once to evaluate flips (O(n^2)), resulting in O(n^2) total time

Space Complexity: O(n^2) We store island labels in an n×n grid (O(n^2)), island sizes in a map (O(number of islands)), and DFS recursion stack (O(n^2) worst case)

What We've Learned

Connected component labeling with metadata: When you need to merge or analyze groups in a grid, use DFS/BFS to label each component with a unique ID and store its size in a hashmap - this transforms an O(n²) merge query into O(1) lookup, enabling efficient "what-if" analysis without re-traversing.
Neighbor deduplication with sets: When summing sizes of adjacent islands around a cell, use a set to track unique island IDs before summing - this prevents double-counting when the same island touches a cell from multiple directions (e.g., an L-shaped island touching from north and east).
Two-phase grid processing pattern: Separate preprocessing (label all components) from query evaluation (test each flip) - this amortizes the cost of component discovery across all potential modifications, turning an O(n⁴) brute force into O(n²).
All-ones edge case handling: Always check if the grid has no zeros at all before processing - return n² immediately, as the flip logic assumes at least one zero exists and will fail or return incorrect results on a completely filled grid.
Island merging formula: For each zero cell, the potential island size is 1 (the flipped cell) + sum of unique neighboring island sizes - this captures the insight that flipping connects previously disconnected components through a single bridge point.
Grid modification without mutation: Instead of actually flipping cells and recalculating, precompute all component metadata once and simulate flips through arithmetic - this read-only approach is faster, parallelizable, and easier to debug than repeatedly modifying state.

Test Your Understanding

Why is matrix the right data structure for this problem?

matrix provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early November, 2025

Meta

Mid-level

Late October, 2025

Meta

Staff

same question but instead of island, it's bomb.

Early October, 2025

Meta

Staff

Get Premium to View All 20+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 827. Making A Large Island

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact