# LC 827. Making A Large Island

### [Problem link](https://leetcode.com/problems/making-a-large-island/)

###### tags: `leedcode` `hard` `c++` `DFS`

You are given an <code>n x n</code> binary matrix <code>grid</code>. You are allowed to change **at most one** <code>0</code> to be <code>1</code>.

Return the size of the largest **island** in <code>grid</code> after applying this operation.

An **island** is a 4-directionally connected group of <code>1</code>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:**

- <code>n == grid.length</code>
- <code>n == grid[i].length</code>
- <code>1 <= n <= 500</code>
- <code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.

## Solution 1 - DFS
#### C++

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int x, int y, int idx) {
        int n = grid.size();
        int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
        grid[x][y] = idx;
        int area = 1;

        for (int i = 0; i < 4; i++) {
            int newX = x + dir[i][0];
            int newY = y + dir[i][1];
            if (0 <= newX && newX < n && 0 <= newY && newY < n && grid[newX][newY] == 1) {
                area += dfs(grid, newX, newY, idx);
            }
        }
        return area;
    }

    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        unordered_map<int, int> umap;
        int idx = 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int area = dfs(grid, i, j, idx);
                    umap[idx] = area;
                    idx++;
                }
            }
        }

        int res = 0;
        for (auto& p: umap) {
            res = max(res, p.second);
        }
        int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    int tmp = 1;
                    unordered_set<int> r;
                    for (int k = 0; k < 4; k++) {
                        int newX = i + dir[k][0];
                        int newY = j + dir[k][1];
                        if (0 <= newX && newX < n && 0 <= newY && newY < n && r.find(grid[newX][newY]) == r.end()) {
                            tmp += umap[grid[newX][newY]];
                            r.insert(grid[newX][newY]);
                        }
                    }
                    res = max(res, tmp);
                }
            }
        }
        return res;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n^2) | O(n^2) |

## Note
x