Making A Large Island

Problem Statement

In computational geometry and graph theory, we often deal with the concept of connectivity on grids. In this problem, you are given a square binary matrix grid of size n x n, where each cell contains either a 0 or a 1. The challenge is to identify the largest possible "island" or contiguous block of 1s after you are permitted to change at most one 0 to a 1. An island is defined as a group of 1s that are connected horizontally or vertically (4-directionally). This task tests your ability to manipulate and analyze two-dimensional arrays, optimizing for connectivity after a single, strategic modification.

Examples

Example 1

Input:

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

Output:

3

Explanation:

Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Example 2

Input:

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

Output:

4

Explanation:

Change the 0 to 1 and make the island bigger, only one island with area = 4.

Example 3

Input:

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

Output:

4

Explanation:

Can't change any 0 to 1, only one island with area = 4.

Constraints

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

Approach and Intuition

The problem involves identifying and potentially expanding the largest contiguous group of 1s in a binary matrix, with the allowance to convert one 0 to 1. Here is a step-by-step approach to solve the problem:

1. Identify All Islands:

   • Use a depth-first search (DFS) or breadth-first search (BFS) to traverse the grid and identify all distinct islands. During this process, mark the cells that belong to the same island with a unique identifier.

2. Calculate Island Sizes:

   • While identifying islands, maintain a count of the number of 1s in each island. Store these sizes in a dictionary or array, where the key/index represents the unique identifier of the island and the value represents its size.

3. Consider the Conversion of 0 to 1:

   • For every 0 in the grid, imagine converting it to 1. Check all four possible 4-directional neighbors of this cell:
     • If a neighbor is a 1, note down which island this neighbor belongs to.
     • Assess whether converting this 0 connects two or more different islands.

4. Calculate the Potential Max Size:

   • For each 0, sum the sizes of all unique neighboring islands. Add 1 (representing the 0 that could be converted). This sum reflects the potential new size of an island if the 0 at this location is converted to 1.

5. Determine the Maximum:

   • Track the maximum island size achieved by converting each 0. Compare it to the largest existing island size to determine the overall maximum size possible.

The approach essentially involves two major sweeps over the grid: one for identifying islands and their sizes, and another for evaluating the impact of changing each 0 to a 1 on the size of contiguous 1s. This method ensures that all possibilities are considered, leveraging the spatial relationships in a grid to derive the optimal solution.

Solutions

class UnionFind {
public:
    vector<int> leader;
    vector<int> rank;
    
    UnionFind(int n) {
        leader.resize(n);
        rank.resize(n, 1);
        for (int i = 0; i < n; i++) {
            leader[i] = i;
        }
    }
    
    int find(int x) {
        if (leader[x] != x) {
            leader[x] = find(leader[x]);
        }
        return leader[x];
    }
    
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;
        if (rank[rootX] < rank[rootY]) {
            leader[rootX] = rootY;
            rank[rootY] += rank[rootX];
        } else {
            leader[rootY] = rootX;
            rank[rootX] += rank[rootY];
        }
    }
};
    
class Solution {
public:
    int largestIsland(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        UnionFind uf(m * n);
        vector<int> dr = {0, 0, 1, -1};
        vector<int> dc = {1, -1, 0, 0};
    
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    int id = n * i + j;
                    for (int d = 0; d < 4; ++d) {
                        int ni = i + dr[d];
                        int nj = j + dc[d];
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                            int nid = n * ni + nj;
                            uf.unite(id, nid);
                        }
                    }
                }
            }
        }
    
        int maxSize = 0;
        bool zeroPresent = false;
        unordered_set<int> uniqueRoots;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    zeroPresent = true;
                    int newSize = 1;
                    for (int d = 0; d < 4; ++d) {
                        int ni = i + dr[d];
                        int nj = j + dc[d];
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                            int nid = n * ni + nj;
                            int root = uf.find(nid);
                            if (uniqueRoots.insert(root).second) {
                                newSize += uf.rank[root];
                            }
                        }
                    }
                    maxSize = max(maxSize, newSize);
                    uniqueRoots.clear();
                }
            }
        }
    
        return zeroPresent ? maxSize : m * n;
    }
};