827. Making A Large Island

HardDepth-First SearchBreadth-First SearchUnion FindArrayMatrix
Leetcode Link

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.

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 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.

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:

  1. Initialization:

    • The solution starts by initializing two lists: p and size.
    • p is the parent list where p[x] represents the parent (or root) of element x. 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 has x as its root. Initially, each cell is its own island with size 1.

  2. Union Operation:

    • The union function takes two elements a and b, 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 element a.
    • This is done by setting the parent of pa to pb and updating the size of pb to include the size of pa.

  3. Find Operation:

    • The find function is used to find the root of the given element x. 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.

  4. 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.

  5. Simulation of Changing 0 to 1:

    • For each cell with a 0, the solution checks the possibility of converting it to 1 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 in vis set), its size is added to a temporary variable t.
    • After considering all neighbors, the potential largest island size (t) is compared with the current answer (ans), and ans is updated if t is larger.

  6. 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 Evaluator

Example 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:

  1. Initialization: The parent list p and size list size 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

  2. 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 are 0, 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 and size lists remain unchanged as each land cell has no adjacent land cells to union with.

  3. Find Operation: Not needed yet since we have not performed any unions and each cell is still its own parent.

  4. Processing the Grid: While iterating through the grid, we found no adjacent islands so the p and size don't change.

  5. Simulation of Changing 0 to 1: Now we try to change each 0 to 1 and calculate the potential size of larger islands:

    • For cell (0,1), if we change 0 to 1, it connects two islands at (0,0) and (0,2). The potential island size will be size[find(0)] + size[find(2)] + 1 = 1 + 1 + 1 = 3.

    • For cell (1,0), if we change 0 to 1, it connects the island at (0,0) and (1,1). The potential island size will be size[find(0)] + size[find(4)] + 1 = 1 + 1 + 1 = 3.

    • For cell (1,2), if we change 0 to 1, it connects the islands at (0,2) and (1,1). The potential island size will be size[find(2)] + size[find(4)] + 1 = 1 + 1 + 1 = 3.

    • For cell (2,1), if we change 0 to 1, it connects the islands at (2,0) and (2,2). The potential island size will be size[find(6)] + size[find(8)] + 1 = 1 + 1 + 1 = 3.

    No other 0 can improve the potential island size past 3. ans is updated accordingly during the process.

  6. Result: The algorithm finishes evaluating all the cells where 0 could be converted to 1. The maximum potential island size remains 3, 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};
74
1// 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}
79

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 p and size array size, which takes O(n^2) time since there are n * n elements in the grid.
  • The union-find operations (find and union functions) are called for each cell connected to its neighboring cells. There are at most 2 calls for union per cell (for the top and left neighbours if they are part of an island), each taking effectively O(1) time on average due to path compression. So, this step costs O(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 find is called to determine the unique root of each neighboring 1-cell. These find operations are also effectively O(1) on average, and the number of checks is 4 per cell at most, leading to another O(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 p and size array size each require O(n^2) space.
  • The vis set 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 find function could be O(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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following is a min heap?

Recommended Readings

DFS Fundamentals

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

BFS Fundamentals

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

DSU/Union Find Fundamentals

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

Want a Structured Path to Master System Design Too? Don’t Miss This!