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 1s that are connected horizontally or vertically (4-directionally). The size of an island is the number of 1s that make up the island. We are to return the size of the largest island after the conversion.
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 1s, 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.
Breadth first search can be used to find the shortest path between two nodes in a directed graph.
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:
pandsize. pis the parent list wherep[x]represents the parent (or root) of elementx. Initially, each cell is its own parent.sizeis 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 hasxas its root. Initially, each cell is its own island with size1.
- The solution starts by initializing two lists:
-
Union Operation:
- The
unionfunction takes two elementsaandb, 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
bis increased by the size of the root of the first elementa. - This is done by setting the parent of
patopband updating thesizeofpbto include thesizeofpa.
- The
-
Find Operation:
- The
findfunction 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
findoperations.
- 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 to1and 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 invisset), 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), andansis updated iftis 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.
Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Example Walkthrough
Let's use a small 3x3 example grid to illustrate the solution approach:
1Grid: 21 0 1 30 1 0 41 0 1
We will follow the key elements of the implementation:
-
Initialization: The parent list
pand size listsizeare initialized:1p = [0, 1, 2, 3, 4, 5, 6, 7, 8] // index represents the cell, value represents the parent 2size = [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
pandsizelists 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
pandsizedon't change. -
Simulation of Changing 0 to 1: Now we try to change each
0to1and calculate the potential size of larger islands:-
For cell (0,1), if we change
0to1, 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
0to1, 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
0to1, 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
0to1, 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
0can improve the potential island size past3.ansis updated accordingly during the process. -
-
Result: The algorithm finishes evaluating all the cells where
0could 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
601class 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}
841class 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};
741// Helper function to perform depth-first search starting from a cell (i, j)
2function depthFirstSearch(i: number, j: number, path: [number, number][], grid: number[][], visited: boolean[][], n: number): void {
3 // Boundary check and ensuring it is an unvisited land cell
4 if (i < 0 || j < 0 || i >= n || j >= n || visited[i][j] || grid[i][j] !== 1) {
5 return;
6 }
7
8 // Mark as visited
9 visited[i][j] = true;
10
11 // Include this cell in the current path
12 path.push([i, j]);
13
14 // Explore neighboring cells in all four directions
15 depthFirstSearch(i + 1, j, path, grid, visited, n);
16 depthFirstSearch(i, j + 1, path, grid, visited, n);
17 depthFirstSearch(i - 1, j, path, grid, visited, n);
18 depthFirstSearch(i, j - 1, path, grid, visited, n);
19}
20
21// Main function to find the largest island by 'flipping' one zero to one
22function largestIsland(grid: number[][]): number {
23 const n = grid.length; // Grid dimension
24
25 // Initialize visited and group matrices
26 const visited = Array.from({ length: n }, () => new Array(n).fill(false));
27 const group = Array.from({ length: n }, () => new Array(n).fill(0));
28
29 let groupId = 1; // Assign unique id to each island group
30
31 // Iterate over the grid to perform DFS and group the islands
32 for (let i = 0; i < n; i++) {
33 for (let j = 0; j < n; j++) {
34 const path: [number, number][] = [];
35 depthFirstSearch(i, j, path, grid, visited, n);
36 if (path.length !== 0) {
37 for (const [x, y] of path) {
38 group[x][y] = groupId; // Assign group id to each cell in the island
39 grid[x][y] = path.length; // Update each cell with the size of its island
40 }
41 groupId++;
42 }
43 }
44 }
45
46 // After grouping, calculate the maximum size of an island after flipping one '0' to '1'
47 let maxSize = 0;
48 for (let i = 0; i < n; i++) {
49 for (let j = 0; j < n; j++) {
50 // If current cell is '0' (water), check adjacent cells to potentially flip it
51 if (grid[i][j] === 0) {
52 let sum = 1; // After flipping, it becomes '1'
53 const uniqueGroups = new Set<number>();
54 // Check all adjacent cells and sum the sizes of distinct island groups
55 if (i > 0 && !uniqueGroups.has(group[i - 1][j])) {
56 sum += grid[i - 1][j];
57 uniqueGroups.add(group[i - 1][j]);
58 }
59 if (i < n - 1 && !uniqueGroups.has(group[i + 1][j])) {
60 sum += grid[i + 1][j];
61 uniqueGroups.add(group[i + 1][j]);
62 }
63 if (j > 0 && !uniqueGroups.has(group[i][j - 1])) {
64 sum += grid[i][j - 1];
65 uniqueGroups.add(group[i][j - 1]);
66 }
67 if (j < n - 1 && !uniqueGroups.has(group[i][j + 1])) {
68 sum += grid[i][j + 1];
69 }
70 maxSize = Math.max(maxSize, sum); // Update the maximum island size
71 } else {
72 // If it's already a '1', consider the size of the current island
73 maxSize = Math.max(maxSize, grid[i][j]);
74 }
75 }
76 }
77 return maxSize; // Return the maximum island size found
78}
79How many times is a tree node visited in a depth first search?
Time and Space Complexity
Time Complexity
The given code implements a union-find algorithm to solve the problem of finding the largest island after changing a 0 to a 1 on a grid.
- First, it initializes union-find structures such as the parent array
pand size arraysize, which takesO(n^2)time since there aren * nelements in the grid. - The union-find operations (
findandunionfunctions) are called for each cell connected to its neighboring cells. There are at most 2 calls forunionper cell (for the top and left neighbours if they are part of an island), each taking effectivelyO(1)time on average due to path compression. So, this step costsO(n^2)in total. - The last nested for loops check all cells again to calculate the size of the largest possible island by changing one 0 to a 1. For each 0, up to 4 neighboring cells are checked, and
findis called to determine the unique root of each neighboring 1-cell. Thesefindoperations are also effectivelyO(1)on average, and the number of checks is 4 per cell at most, leading to anotherO(n^2)operation.
Considering these steps, the dominant term in the time complexity is O(n^2), with the constant factors from the union-find operations being relatively low due to path compression and union by size/rank heuristics.
The time complexity is \(\mathcal{O}(n^2)\).
Space Complexity
- The parent array
pand size arraysizeeach requireO(n^2)space. - The
visset in the last nested for loops can contain at most 4 elements in any one iteration, however, it's cleared after considering a single cell, so it does not contribute significantly to the space complexity. - The space taken by the stack due to recursive calls in the
findfunction could beO(n^2)in the worst case without path compression, however with path compression, the depth of the recursion tree is greatly reduced. This also means the effective space complexity due to recursion is much less on average.
In conclusion, the primary space complexity is due to the storage of elements in the union-find structure: \(\mathcal{O}(n^2)\).
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement recursion?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.