How do you solve Making A Large Island on LeetCode?

Making A Large Island (LeetCode #827) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Labeling islands allows us to efficiently calculate potential sizes when changing a 0 to 1.

What is the brute force solution for Making A Large Island?

The brute force approach for Making A Large Island is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every cell in the grid. For each 0, we temporarily change it to 1 and calculate the size of the island formed. This is simple but inefficient, especially for larger grids. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Making A Large Island?

Making A Large Island uses the following concepts: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix. The recommended patterns to study are: Depth-First Search (DFS), Hash Map, Matrix Traversal.

What are the interview tips for Making A Large Island?

Explain your thought process clearly while coding, especially when handling edge cases. Consider both time and space complexity when discussing your approach. Practice explaining your solution as if teaching someone else; this helps clarify your understanding.

What are common mistakes when solving Making A Large Island?

Forgetting to restore the grid after changing a 0 to 1 in the brute force approach. Not considering all neighboring islands when calculating potential sizes.

#827

Making A Large Island

Hard

ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrixDepth-First Search (DFS)Hash MapMatrix Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

The optimal solution uses a combination of DFS to label islands and a HashMap to store the sizes of each island. This allows us to efficiently calculate the potential size of the largest island when changing a 0 to 1 by checking neighboring islands.

⚙️

Algorithm

3 steps

1Step 1: Use DFS to label each island and store their sizes in a HashMap.
2Step 2: Iterate through the grid again. For each 0, check its 4 neighbors to find unique island IDs and sum their sizes.
3Step 3: Return the maximum size found, plus one for the 0 that can be changed to 1.

solution.py40 lines

1# Full working Python code
2
3def largestIsland(grid):
4    n = len(grid)
5    island_id = 2  # Start labeling islands from 2
6    sizes = {}  # To store sizes of islands
7
8    def dfs(x, y, id):
9        if x < 0 or x >= n or y < 0 or y >= n or grid[x][y] != 1:
10            return 0
11        grid[x][y] = id  # Label the island
12        size = 1
13        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
14            size += dfs(x + dx, y + dy, id)
15        return size
16
17    for i in range(n):
18        for j in range(n):
19            if grid[i][j] == 1:
20                sizes[island_id] = dfs(i, j, island_id)
21                island_id += 1
22
23    max_size = max(sizes.values(), default=0)
24    result = max_size  # If no 0s, return max_size
25
26    for i in range(n):
27        for j in range(n):
28            if grid[i][j] == 0:
29                seen = set()
30                current_size = 1  # Start with changing this 0 to 1
31                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
32                    ni, nj = i + dx, j + dy
33                    if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] > 1:
34                        seen.add(grid[ni][nj])
35                for id in seen:
36                    current_size += sizes[id]
37                result = max(result, current_size)
38
39    return result
40

ℹ

Complexity note: The time complexity is O(n²) due to the need to traverse the entire grid for both labeling islands and checking potential sizes. The space complexity is O(n) because we store the sizes of islands in a HashMap.

1Labeling islands allows us to efficiently calculate potential sizes when changing a 0 to 1.
2Using a HashMap to store island sizes helps avoid redundant calculations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.