# Making A Large Island
**Difficulty:** HARD
[External](https://leetcode.com/problems/making-a-large-island)
Canonical: https://scaleengineer.com/dsa/problems/making-a-large-island
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Matrix
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [DoorDash](https://scaleengineer.com/companies/doordash), [Snowflake](https://scaleengineer.com/companies/snowflake), [jio](https://scaleengineer.com/companies/jio), [Snap](https://scaleengineer.com/companies/snap), [UiPath](https://scaleengineer.com/companies/uipath), [Anduril](https://scaleengineer.com/companies/anduril)
---
## Problem
You are given an `n x n` binary matrix `grid`. You are allowed to change **at most one** `0` to be `1`.

Return _the size of the largest **island** in_ `grid` _after applying this operation_.

An **island** is a 4-directionally connected group of `1`s.

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

# Approaches
## Brute Force by Flipping Each Zero
The most straightforward approach is to simulate the process directly. We can iterate through every cell in the grid. If a cell contains a `0`, we temporarily change it to a `1` and then calculate the size of the largest island in this newly modified grid. We keep track of the maximum size found across all these simulations.
**Time:** O(n^4). Let `N = n*n`. There are `O(N)` cells. For each of the `O(N)` cells that could be a zero, we perform a full grid traversal to find the largest island, which takes `O(N)` time. This results in a total time complexity of `O(N*N) = O((n^2)^2) = O(n^4)`. · **Space:** O(n^2). The space is dominated by the `visited` array used in the island size calculation function and the recursion stack for DFS, both of which can be O(n^2) in the worst case.
**Pros:** Simple to understand and implement.; Directly simulates the problem statement.
**Cons:** Highly inefficient due to redundant calculations.; For each `0` that is flipped, it re-scans the entire grid and re-calculates island sizes from scratch.; Will likely result in a "Time Limit Exceeded" error for larger grids as specified in the constraints.
### Explanation
This method involves a nested loop to traverse the grid. For each cell `(r, c)` containing a `0`, we perform the following steps:
1. Flip `grid[r][c]` from `0` to `1`.
2. Trigger a function to find the largest island size in the current state of the grid. This function itself would iterate through all cells, and for each unvisited `1`, it would start a traversal (like Depth First Search or Breadth First Search) to find the size of the island it belongs to. A `visited` matrix is required to avoid recounting.
3. Update a global maximum size variable with the result from step 2.
4. Flip `grid[r][c]` back to `0` to restore the grid for the next iteration.

An initial check is needed for the case where the grid contains no zeros. In this scenario, the answer is simply the size of the single island, which is `n*n`.

```java
class Solution {
    public int largestIsland(int[][] grid) {
        int n = grid.length;
        int maxArea = 0;
        boolean hasZero = false;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    hasZero = true;
                    grid[i][j] = 1; // Flip 0 to 1
                    maxArea = Math.max(maxArea, findLargestIslandSize(grid));
                    grid[i][j] = 0; // Flip back
                }
            }
        }

        return hasZero ? maxArea : n * n;
    }

    private int findLargestIslandSize(int[][] grid) {
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    maxArea = Math.max(maxArea, dfs(i, j, grid, visited));
                }
            }
        }
        return maxArea;
    }

    private int dfs(int r, int c, int[][] grid, boolean[][] visited) {
        int n = grid.length;
        if (r < 0 || r >= n || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {
            return 0;
        }
        visited[r][c] = true;
        int count = 1;
        count += dfs(r + 1, c, grid, visited);
        count += dfs(r - 1, c, grid, visited);
        count += dfs(r, c + 1, grid, visited);
        count += dfs(r, c - 1, grid, visited);
        return count;
    }
}
```
### Algorithm
- Initialize `maxSize = 0`.
- Initialize a boolean flag `hasZero = false` to track if any `0` exists in the grid.
- Iterate through each cell `(r, c)` of the `n x n` grid.
- If `grid[r][c] == 0`:
  - Set `hasZero = true`.
  - Temporarily change `grid[r][c]` to `1`.
  - Call a helper function `calculateLargestIsland(grid)` to find the size of the largest island in the modified grid. This helper function uses a standard DFS/BFS traversal with a `visited` array to explore and count connected `1`s.
  - Update `maxSize = max(maxSize, calculatedSize)`.
  - Revert `grid[r][c]` back to `0` to restore the grid for the next iteration.
- After the loops, if `hasZero` is `false`, it means the grid was all `1`s, so the answer is `n*n`. Otherwise, the answer is `maxSize`.

## Two-Pass with Component Labeling
A much more efficient approach involves two main passes over the grid. The first pass identifies all existing islands, assigns each a unique ID, and calculates and stores its size. The second pass iterates through all the `0`s in the grid. For each `0`, it checks its neighboring cells to see which unique islands it could connect. By summing the sizes of these unique neighboring islands and adding 1 (for the `0` itself), we can find the potential size of the new, larger island.
**Time:** O(n^2). Let `N = n*n`. Pass 1 involves a full grid traversal where each cell is visited once (DFS/BFS), taking `O(N)` time. Pass 2 involves another full grid traversal, and for each cell, the work is constant (checking 4 neighbors). This also takes `O(N)` time. The total time is `O(N) + O(N) = O(N) = O(n^2)`. · **Space:** O(n^2). The space is used for the `islandSizes` map, which can store up to O(n^2) entries in the worst case (a checkerboard pattern). The recursion stack for the DFS can also go up to O(n^2) in the worst case (a snake-like island).
**Pros:** Very efficient, with a linear time complexity relative to the grid size.; Avoids redundant computations by pre-calculating and storing island properties.; Passes for large inputs where brute-force would fail.
**Cons:** More complex to implement than the brute-force approach.; Requires modifying the input grid or using an auxiliary grid, which increases space complexity if the input is immutable.
### Explanation
This method avoids the redundant calculations of the brute-force approach by pre-computing the sizes of all initial islands.

**Pass 1: Find and Label Islands**
We traverse the grid. When we encounter a `1` that hasn't been labeled, we start a traversal (DFS or BFS). We assign a new, unique `islandId` (e.g., starting from 2, to not conflict with `0` and `1`). During the traversal, we find all connected `1`s, count them to get the island's `size`, and update the grid cells of this island from `1` to `islandId`. We store the mapping of `islandId` to `size` in a hash map. We also find the largest island size found during this pass, which handles the edge case where the grid has no `0`s.

**Pass 2: Evaluate Zeros**
We traverse the grid again, this time looking for `0`s. For each `0`, we look at its four neighbors and collect their unique `islandId`s. The potential new island size is `1` (for the `0` we flip) plus the sum of the sizes of all unique neighboring islands. We update our overall maximum size with this potential size.

```java
class Solution {
    public int largestIsland(int[][] grid) {
        int n = grid.length;
        // map: islandId -> islandSize
        Map<Integer, Integer> islandSizes = new HashMap<>();
        int islandId = 2; // Start island IDs from 2

        // Pass 1: Find all islands, label them, and store their sizes.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) { // Found an unlabeled island
                    int size = paint(i, j, grid, islandId);
                    islandSizes.put(islandId, size);
                    islandId++;
                }
            }
        }

        // If no islands were found, the grid is all zeros. The largest we can make is 1.
        if (islandSizes.isEmpty()) {
            return 1;
        }

        int maxArea = 0;
        // Get the size of the largest existing island. This handles the all-1s case.
        for (int size : islandSizes.values()) {
            maxArea = Math.max(maxArea, size);
        }

        // Pass 2: Iterate through zeros and calculate potential merged island size.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> neighborIds = new HashSet<>();
                    // Check 4-directional neighbors
                    if (i > 0) neighborIds.add(grid[i - 1][j]);
                    if (i < n - 1) neighborIds.add(grid[i + 1][j]);
                    if (j > 0) neighborIds.add(grid[i][j - 1]);
                    if (j < n - 1) neighborIds.add(grid[i][j + 1]);
                    
                    int potentialArea = 1; // For the zero itself
                    for (int id : neighborIds) {
                        if (id > 1) { // It's a valid island ID
                            potentialArea += islandSizes.get(id);
                        }
                    }
                    maxArea = Math.max(maxArea, potentialArea);
                }
            }
        }
        
        return maxArea;
    }

    // Helper function to find an island, paint it with an ID, and return its size.
    private int paint(int r, int c, int[][] grid, int islandId) {
        int n = grid.length;
        if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1) {
            return 0;
        }
        grid[r][c] = islandId;
        return 1 + paint(r + 1, c, grid, islandId)
                 + paint(r - 1, c, grid, islandId)
                 + paint(r, c + 1, grid, islandId)
                 + paint(r, c - 1, grid, islandId);
    }
}
```
### Algorithm
- Initialize a map `islandSizes` to store `islandId -> size` and an `islandId` counter starting from 2.
- **Pass 1: Labeling**
  - Iterate through each cell `(r, c)` of the grid.
  - If `grid[r][c] == 1`, it's a new, unlabeled island.
  - Start a DFS/BFS from `(r, c)`.
  - During the traversal, change all `1`s of the island to the current `islandId` and count the number of cells (`size`).
  - Store the result: `islandSizes.put(islandId, size)`.
  - Increment `islandId` for the next island.
- Handle edge case: If `islandSizes` is empty after Pass 1, the grid was all `0`s. Return `1` (since we can flip one `0`).
- Initialize `maxSize` to the largest value in `islandSizes.values()`. This covers the case where no `0`s can be flipped.
- **Pass 2: Merging**
  - Iterate through each cell `(r, c)` of the grid.
  - If `grid[r][c] == 0`:
    - Create a `Set` to store the unique `islandId`s of its 4-directional neighbors.
    - Calculate `potentialSize = 1` (for the current `0`).
    - For each unique `islandId` in the set, add its corresponding size from the `islandSizes` map to `potentialSize`.
    - Update `maxSize = max(maxSize, potentialSize)`.
- Return `maxSize`.

# Solutions
### Java

```java
class Solution {
private
  int n;
private
  int[] p;
private
  int[] size;
private
  int ans = 1;
private
  int[] dirs = new int[]{-1, 0, 1, 0, -1};
public
  int largestIsland(int[][] grid) {
    n = grid.length;
    p = new int[n * n];
    size = new int[n * n];
    for (int i = 0; i < p.length; ++i) {
      p[i] = i;
      size[i] = 1;
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {
              int pa = find(x * n + y), pb = find(i * n + j);
              if (pa == pb) {
                continue;
              }
              p[pa] = pb;
              size[pb] += size[pa];
              ans = Math.max(ans, size[pb]);
            }
          }
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 0) {
          int t = 1;
          Set<Integer> vis = new HashSet<>();
          for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {
              int root = find(x * n + y);
              if (!vis.contains(root)) {
                vis.add(root);
                t += size[root];
              }
            }
          }
          ans = Math.max(ans, t);
        }
      }
    }
    return ans;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### CPP

```cpp
class Solution {
public:
  const static inline vector<int> dirs = {-1, 0, 1, 0, -1};
  int largestIsland(vector<vector<int>> &grid) {
    int n = grid.size();
    vector<int> p(n * n);
    vector<int> size(n * n, 1);
    iota(p.begin(), p.end(), 0);
    function<int(int)> find;
    find = [&](int x) {
      if (p[x] != x) {
        p[x] = find(p[x]);
      }
      return p[x];
    };
    int ans = 1;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j]) {
          for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y]) {
              int pa = find(x * n + y), pb = find(i * n + j);
              if (pa == pb)
                continue;
              p[pa] = pb;
              size[pb] += size[pa];
              ans = max(ans, size[pb]);
            }
          }
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (!grid[i][j]) {
          int t = 1;
          unordered_set<int> vis;
          for (int k = 0; k < 4; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y]) {
              int root = find(x * n + y);
              if (!vis.count(root)) {
                vis.insert(root);
                t += size[root];
              }
            }
          }
          ans = max(ans, t);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def union(a, b): pa, pb = find(a), find(b) if pa == pb: return p[pa] = pb size[pb] += size[pa] n = len(grid) p = list(range(n * n)) size = [1] * (n * n) for i, row in enumerate(grid): for j, v in enumerate(row): if v: for a, b in [[0, - 1], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < n and 0 <= y < n and grid[x][y]: union(x * n + y, i * n + j) ans = max(size) for i, row in enumerate(grid): for j, v in enumerate(row): if v == 0: vis = set() t = 1 for a, b in [[0, - 1], [0, 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < n and 0 <= y < n and grid[x][y]: root = find(x * n + y) if root not in vis: vis . add(root) t += size[root] ans = max(ans, t) return ans

```