827. Making A Large Island
Problem Description
In this problem, we are given a square binary matrix grid
where each cell is either 0
(representing water) or 1
(representing land). The task is to convert at most one 0
to 1
, effectively "creating" additional land, and then determine the size of the largest "island" that results. An island is defined as a group of 1
s that are connected horizontally or vertically (4-directionally). The size of an island is the number of 1
s that make up the island. We are to return the size of the largest island after the conversion.
Flowchart Walkthrough
Let's analyze LeetCode 827. Making A Large Island using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: The grid in this problem can be conceptualized as a graph, where each cell is a node and edges exist between adjacent cells with value 1.
Is it a tree?
- No: The grid may contain multiple connected components of 1s. There isn't a unique parent-child relationship that characterizes a tree.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The problem involves finding the largest connected island by potentially flipping one cell value, and there are cycles in these connections.
Is the problem related to shortest paths?
- No: The objective is to find the largest connected component, not the shortest path between nodes.
Does the problem involve connectivity?
- Yes: The challenge involves determining the size of connected groups of cells and the effect of changing one cell on these connections.
Is the graph weighted?
- No: There are no weights associated with the cells; each cell is simply marked as either land (1) or water (0).
Conclusion: According to the flowchart, for an unweighted connectivity problem, Depth-First Search (DFS) is the suitable approach. DFS is effective for exploring and marking all nodes in a connected component, and it can efficiently compute the sizes of these components, which is crucial for solving this problem by trying to create the largest possible island.
Intuition
The intuition behind the solution is to first understand what constitutes an island and how we can measure its size. Since an island is a group of connected 1
s, we can use Depth First Search (DFS), Breadth First Search (BFS), or Union-Find algorithm to identify all the islands and their sizes before making any changes to the grid.
The Union-Find algorithm is an efficient algorithm to group elements into disjoint sets and is particularly useful in this scenario for keeping track of which cells (land tiles) belong to which island. Following this, we initialize each cell as its own parent (representative of its own set), and if a cell is part of an island, we perform a union operation to link it with its neighboring island cells.
After doing this for the entire grid, we can now consider each 0
and simulate changing it to a 1
. When we convert a 0
to a 1
, we must look at its 4-directional neighbors. If these neighbors are part of different islands, we can potentially join those islands together, thereby increasing the size of the resulting island. Therefore, for each 0
, we determine the unique islands of its neighbors, sum up their sizes (since converting the 0
to 1
would connect them), and then track the largest size achieved by this operation.
The key steps within this approach are to use the Union-Find algorithm to group the islands and then iterate over the grid to find the best place to convert a 0
to 1
to maximize the island size.
We return the size of the largest island after considering the conversion of one 0
to 1
. Note that it’s important to handle special cases separately, such as when there is no 0
in the grid or when the entire grid is water.
Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.
Solution Approach
The provided solution implements the Union-Find algorithm which is well-suited for dynamic connectivity problems like this one. The Union-Find algorithm helps to efficiently join islands and track their size throughout the process.
Here are the key elements of the implementation:
-
Initialization:
- The solution starts by initializing two lists:
p
andsize
. p
is the parent list wherep[x]
represents the parent (or root) of elementx
. Initially, each cell is its own parent.size
is a list that represents the size of the tree (or island in this case) for which the index is the root. Therefore,size[x]
is the size of the set that hasx
as its root. Initially, each cell is its own island with size1
.
- The solution starts by initializing two lists:
-
Union Operation:
- The
union
function takes two elementsa
andb
, finds their respective roots, and combines the sets they belong to (if they are in different sets). - When union is performed, the size of the root of the second element
b
is increased by the size of the root of the first elementa
. - This is done by setting the parent of
pa
topb
and updating thesize
ofpb
to include thesize
ofpa
.
- The
-
Find Operation:
- The
find
function is used to find the root of the given elementx
. It does this by traversing the parent pointers until it reaches the root. - Path compression is used here: during this traversal, the parent of all visited elements is updated to the root, which flattens the structure and speeds up future
find
operations.
- The
-
Processing the Grid:
- The solution iterates over the grid to update parent and size lists based on the initial 1's locations. It uses union operations to merge adjacent lands into single islands.
- This is achieved by checking the North (
[-1, 0]
) and West ([0, -1]
) neighbors of each cell, as Eastern and Southern neighbors will be checked when the iteration reaches those cells.
-
Simulation of Changing 0 to 1:
- For each cell with a
0
, the solution checks the possibility of converting it to1
and calculates the potential size of the resulting island. - It examines the 4-directional neighbors and if any are
1
, it finds the root of that neighboring island. If the root is not already considered (not invis
set), its size is added to a temporary variablet
. - After considering all neighbors, the potential largest island size (
t
) is compared with the current answer (ans
), andans
is updated ift
is larger.
- For each cell with a
-
Result:
- After all grid positions have been assessed, the maximum value found is returned as the answer.
The algorithm ensures that even if multiple 0
cells are connected to the same island, the island's size is only counted once thanks to the usage of the set vis
. This approach yields the size of the largest possible island that could be created by turning one 0
into a 1
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small 3x3 example grid to illustrate the solution approach:
Grid: 1 0 1 0 1 0 1 0 1
We will follow the key elements of the implementation:
-
Initialization: The parent list
p
and size listsize
are initialized:p = [0, 1, 2, 3, 4, 5, 6, 7, 8] // index represents the cell, value represents the parent size = [1, 1, 1, 1, 1, 1, 1, 1, 1] // Each cell is initially considered its own island of size 1
-
Union Operation: The grid is processed, and union operations are performed for adjacent land cells (i.e., cells with
1
):- For cell (0,0),
1
, it has no Northern or Western land neighbors so it remains a single-island cell. - For cell (0,2),
1
, it has no Northern or Western land neighbors so it remains a single-island cell. - For cell (1,1),
1
, it has land neighbors at (0,1) and (1,0) but those are0
, so no union operation is needed. - For cell (2,0),
1
, it has no Northern or Western land neighbors so it remains a single-island cell. - For cell (2,2),
1
, it has no Northern or Western land neighbors so it remains a single-island cell.
After considering all land cells, our
p
andsize
lists remain unchanged as each land cell has no adjacent land cells to union with. - For cell (0,0),
-
Find Operation: Not needed yet since we have not performed any unions and each cell is still its own parent.
-
Processing the Grid: While iterating through the grid, we found no adjacent islands so the
p
andsize
don't change. -
Simulation of Changing 0 to 1: Now we try to change each
0
to1
and calculate the potential size of larger islands:-
For cell (0,1), if we change
0
to1
, it connects two islands at (0,0) and (0,2). The potential island size will besize[find(0)] + size[find(2)] + 1
=1 + 1 + 1
=3
. -
For cell (1,0), if we change
0
to1
, it connects the island at (0,0) and (1,1). The potential island size will besize[find(0)] + size[find(4)] + 1
=1 + 1 + 1
=3
. -
For cell (1,2), if we change
0
to1
, it connects the islands at (0,2) and (1,1). The potential island size will besize[find(2)] + size[find(4)] + 1
=1 + 1 + 1
=3
. -
For cell (2,1), if we change
0
to1
, it connects the islands at (2,0) and (2,2). The potential island size will besize[find(6)] + size[find(8)] + 1
=1 + 1 + 1
=3
.
No other
0
can improve the potential island size past3
.ans
is updated accordingly during the process. -
-
Result: The algorithm finishes evaluating all the cells where
0
could be converted to1
. The maximum potential island size remains3
, which is the final result returned by the algorithm.
This small example illustrates that by changing any single 0
to a 1
on the grid, we can achieve an island of maximum size 3
, considering horizontal and vertical connections only.
Solution Implementation
1class Solution:
2 def largestIsland(self, grid: List[List[int]]) -> int:
3 # Function to find the root of a set an element belongs to.
4 def find_root(element):
5 # Path compression: update parent during find operation.
6 if parents[element] != element:
7 parents[element] = find_root(parents[element])
8 return parents[element]
9
10 # Function to merge two disjoint sets.
11 def union_sets(set1, set2):
12 # Find the roots of the sets to which the two elements belong.
13 root1, root2 = find_root(set1), find_root(set2)
14 if root1 == root2:
15 # Elements are already in the same set.
16 return
17 # Merge the two sets.
18 parents[root1] = root2
19 # Update the size of the resulting set.
20 set_sizes[root2] += set_sizes[root1]
21
22 n = len(grid)
23 # Initialization of disjoint set union data structure.
24 parents = list(range(n * n))
25 set_sizes = [1] * (n * n)
26
27 # Build the sets for all 1s in the grid (initial islands).
28 for i, row in enumerate(grid):
29 for j, value in enumerate(row):
30 if value:
31 # Try to union with any neighboring 1s to the left and above.
32 for a, b in [[0, -1], [-1, 0]]:
33 x, y = i + a, j + b
34 if 0 <= x < n and 0 <= y < n and grid[x][y]:
35 # Union the current cell with the neighbor.
36 union_sets(x * n + y, i * n + j)
37
38 # Check for the largest initial island size.
39 max_island_size = max(set_sizes)
40
41 # Check every 0 in the grid to see if it converts to 1 leading to larger island.
42 for i, row in enumerate(grid):
43 for j, value in enumerate(row):
44 if value == 0:
45 visited_roots = set() # Track visited roots to prevent double counting.
46 temp_size = 1 # Start with the current cell being converted to 1.
47 # Check all 4 directions around the current cell.
48 for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
49 x, y = i + a, j + b
50 if 0 <= x < n and 0 <= y < n and grid[x][y]:
51 root = find_root(x * n + y)
52 # If we haven't already added the size of this island root, add it now.
53 if root not in visited_roots:
54 visited_roots.add(root)
55 temp_size += set_sizes[root]
56 # Update our answer if we found a larger island.
57 max_island_size = max(max_island_size, temp_size)
58
59 return max_island_size
60
1class Solution {
2 // Instance variables
3 private int gridSize; // The length of the grid
4 private int[] parent; // Parent array for the disjoint-set (Union-Find)
5 private int[] clusterSize; // Size of each cluster in the disjoint-set
6 private int maxIslandSize = 1; // Initialize the result to 1 as minimum island size
7 private int[] directions = new int[] {-1, 0, 1, 0, -1}; // Directions for exploring neighbors
8
9 // Method to calculate the largest island by flipping one zero to one, if possible.
10 public int largestIsland(int[][] grid) {
11 gridSize = grid.length;
12 parent = new int[gridSize * gridSize];
13 clusterSize = new int[gridSize * gridSize];
14
15 // Initialize each point as its own parent and the initial size of 1
16 for (int i = 0; i < parent.length; ++i) {
17 parent[i] = i;
18 clusterSize[i] = 1;
19 }
20
21 // Loop through each cell in the grid to perform Union-Find merge operations
22 for (int i = 0; i < gridSize; ++i) {
23 for (int j = 0; j < gridSize; ++j) {
24 if (grid[i][j] == 1) { // Process only the land cells
25 // Loop to check all 4 possible neighbors
26 for (int k = 0; k < 4; ++k) {
27 // Calculate neighboring coordinates based on current cell
28 int x = i + directions[k];
29 int y = j + directions[k + 1];
30
31 // Check if the neighbor is within the grid and is land
32 if (x >= 0 && x < gridSize && y >= 0 && y < gridSize && grid[x][y] == 1) {
33 int rootNeighbor = find(x * gridSize + y);
34 int rootCurrent = find(i * gridSize + j);
35 // If neighbors belong to different sets, perform union operation
36 if (rootNeighbor != rootCurrent) {
37 parent[rootNeighbor] = rootCurrent;
38 clusterSize[rootCurrent] += clusterSize[rootNeighbor];
39 // Update the max island size
40 maxIslandSize = Math.max(maxIslandSize, clusterSize[rootCurrent]);
41 }
42 }
43 }
44 }
45 }
46 }
47
48 // Consider flipping each zero to one and calculate the potential island size
49 for (int i = 0; i < gridSize; ++i) {
50 for (int j = 0; j < gridSize; ++j) {
51 if (grid[i][j] == 0) { // Process only the water cells
52 int potentialSize = 1; // Initialize the potential size with the flipped cell
53 Set<Integer> visited = new HashSet<>(); // To avoid counting duplicate clusters
54 // Loop through all 4 directions
55 for (int k = 0; k < 4; ++k) {
56 int x = i + directions[k];
57 int y = j + directions[k + 1];
58 // Check for valid neighboring land cell
59 if (x >= 0 && x < gridSize && y >= 0 && y < gridSize && grid[x][y] == 1) {
60 int root = find(x * gridSize + y);
61 // Only count unique roots to prevent double counting
62 if (!visited.contains(root)) {
63 visited.add(root);
64 potentialSize += clusterSize[root];
65 }
66 }
67 }
68 // Update the maximum island size if current flip leads to a larger island
69 maxIslandSize = Math.max(maxIslandSize, potentialSize);
70 }
71 }
72 }
73 return maxIslandSize;
74 }
75
76 // Union-Find's find operation with path compression
77 private int find(int index) {
78 if (parent[index] != index) {
79 parent[index] = find(parent[index]); // Path compression
80 }
81 return parent[index];
82 }
83}
84
1class Solution {
2public:
3 // Define the directions array in a clean and standardized manner.
4 const static inline std::vector<int> DIRECTIONS = { -1, 0, 1, 0, -1 };
5
6 int largestIsland(std::vector<std::vector<int>>& grid) {
7 int n = grid.size(); // Dimension of the grid
8 std::vector<int> parent(n * n); // Parent array for Union-Find
9 std::vector<int> size(n * n, 1); // Size array for Union-Find
10 std::iota(parent.begin(), parent.end(), 0); // Initialize each node as its own parent
11
12 // Union-Find Find function using path compression for efficiency
13 std::function<int(int)> find;
14 find = [&](int x) {
15 if (parent[x] != x) {
16 parent[x] = find(parent[x]);
17 }
18 return parent[x];
19 };
20
21 // Initial maximum island size, a single cell
22 int maxIslandSize = 1;
23
24 // Union islands and compute their sizes
25 for (int i = 0; i < n; ++i) {
26 for (int j = 0; j < n; ++j) {
27 if (grid[i][j]) {
28 // Explore all 4 directions
29 for (int k = 0; k < 4; ++k) {
30 int x = i + DIRECTIONS[k], y = j + DIRECTIONS[k + 1];
31 if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y]) {
32 int parentA = find(x * n + y);
33 int parentB = find(i * n + j);
34 if (parentA != parentB) {
35 parent[parentA] = parentB;
36 size[parentB] += size[parentA];
37 maxIslandSize = std::max(maxIslandSize, size[parentB]);
38 }
39 }
40 }
41 }
42 }
43 }
44
45 // Try flipping each 0 to a 1 to see if we can get larger island
46 for (int i = 0; i < n; ++i) {
47 for (int j = 0; j < n; ++j) {
48 if (!grid[i][j]) {
49 int potentialSize = 1; // Start with the flipped cell itself
50 std::unordered_set<int> visited;
51
52 // Check all 4 neighboring cells
53 for (int k = 0; k < 4; ++k) {
54 int x = i + DIRECTIONS[k], y = j + DIRECTIONS[k + 1];
55 if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y]) {
56 int root = find(x * n + y);
57 // If root hasn't been seen before, count its size
58 if (visited.count(root) == 0) {
59 visited.insert(root);
60 potentialSize += size[root];
61 }
62 }
63 }
64 // Update the maximum island size
65 maxIslandSize = std::max(maxIslandSize, potentialSize);
66 }
67 }
68 }
69
70 // Return the maximum island size found
71 return maxIslandSize;
72 }
73};