> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/making-a-large-island.md).

# Making A Large Island

In a 2D grid of `0`s and `1`s, we change at most one `0` to a `1`.

After, what is the size of the largest island? (An island is a 4-directionally connected group of `1`s).

**Example 1:**

```
Input: [[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: [[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: [[1, 1], [1, 1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
```

Notes:

* `1 <= grid.length = grid[0].length <= 50`.
* `0 <= grid[i][j] <= 1`.

```java
class Solution {
    int[][] islands;

    public int largestIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        islands = new int[m][n];
        Map<Integer, Integer> islandSize = new HashMap<>();
        int id = 2;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // MARK UNINITIALISED island
                if (islands[i][j] == 0 && grid[i][j] == 1) {
                    islandSize.put(id, markerAndCounterDFS(grid, i, j, id));
                    id++;
                }
            }
        }
        // If only 1 island is present
        if (id == 3) {
            if (islandSize.get(2) == m * n)
                return islandSize.get(2);
            return islandSize.get(2) + 1;
        }
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> set = new HashSet<>();
                    int count = 1;
                    for (int[] dir : dirs) {
                        int newX = i + dir[0];
                        int newY = j + dir[1];
                        if (newX >= 0 && newX < m && newY >= 0 && newY < n && islands[newX][newY] != 0) {
                            int islandID = islands[newX][newY];
                            if (!set.contains(islandID)) {
                                count += islandSize.get(islandID);
                                set.add(islandID);
                            }
                        }
                    }
                    max = Math.max(max, count);
                }
            }
        }
        return max;
    }

    int[][] dirs = { { 1, 0 }, { 0, 1 }, { 0, -1 }, { -1, 0 } };

    public int markerAndCounterDFS(int[][] grid, int x, int y, int id) {
        if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == 1 && islands[x][y] == 0) {
            islands[x][y] = id;
            int ans = 1;
            for (int i = 0; i < 4; i++) {
                int newX = x + dirs[i][0];
                int newY = y + dirs[i][1];
                ans += markerAndCounterDFS(grid, newX, newY, id);
            }
            return ans;
        }
        return 0;
    }
}
```