
### Problem Statement

###### Given an n x n binary matrix grid where 0 denotes water and 1 denotes land. We 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 1s.

**INPUT**

- **grid = \[ [1,0],[0,1] ]**

**OUTPUT**

- **3**

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

**Steps To Solve**

- Write out some test cases
  | | | | | |
  | --- | --- | --- | --- | --- |
  0 | 1 | 0 | 1 | 0
  1 | 1 | 0 | 0 | 1
  0 | 0 | 1 | 1 | 0

- Think of solution without code

  - We see that we have 4 islands in the grid and the max size among the island is 3.
  - Can we make this better?
  - Yes , consider that we change 0 in grid[0][0] to 1,then we would have an island of 4 size.
  - Similarly if we change 0 in grid[1][2] to 1, we would have an island of 6 size.
  - In this way we check for all 0's and find the max size among the islands.
  - Our first step will be to segregate different islands and store the size of each island in a map.
  - We can do this by using island id .Our first island id will be 2 as 0 and 1 are already in grid, this will help in segregation of different islands.
  - Once this has been done using DFS our grid will look something like this :-
    | | | | | |
    | --- | --- | --- | --- | --- |
    0 | 2 | 0 | 3 | 0
    2 | 2 | 0 | 0 | 4
    0 | 0 | 5 | 5 | 0
  - While doing this we will store the size of island in our array.
    | ID | Size |
    | --- | --- |
    | 2 | 3 |
    | 3 | 1 |
    | 4 | 1 |
    | 5 | 2 |

  - Now we will loop over the grid again and every time we encounter 0 we compute the island count.
  - To compute island count we check all four direction from position containing 0 and if we get an island we will add its count from our map.
  - Lets compute for grid[0][0] , we see that right and down side of grid[0][0] has island with id 2. So we add size of island 2 i.e 3 to our answer.
  - We will not add 3 twice as both right and down position has same id i.e 2.
  - Finally we add 1 to our answer to account for the current grid position from which we are checking in four directions. So final answer = 3+1 = 4.
  - We will compare this answer with max and if its greater than max we will update our max.
  - Similarly we will check for other 0's.
  - Lets see for grid[1][2] , when we look left of grid[1][2] we see island with id 2 , so we add 3 to our answer , when we look down we see island with id 5 ,so we add 2 to our answer and finally 1 for the grid[1][2] itself.Total = 3 + 2 + 1 = 6. Now we compare this with max if max is less than 6 , we will update our max as 6.
  - Thats it , now lets quickly skip to the solution.

Lets also get a quick look at an image of island distribution to get things much clearer.

![Making a Large Island](https://s3-lc-upload.s3.amazonaws.com/users/votrubac/image_1525310120.png)

Here our max island size is **35**.

```js
var largestIsland = function (grid) {
  let N = grid.length;

  let color = 2,
    res = 0; //since 0 & 1 is already present

  let area = {};
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (grid[i][j] === 1) {
        area[color] = dfs(grid, i, j, color);
        res = Math.max(res, area[color++]);
      }
    }
  }

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (grid[i][j] === 0) {
        let seen = {};
        let curr = 1;
        for (let [p0, p1] of move(i, j)) {
          let index = grid[p0][p1];
          if (index > 1 && !seen.hasOwnProperty(index)) {
            seen[index] = 1;
            curr += area[index];
          }
        }
        res = Math.max(res, curr);
      }
    }
  }

  return res;

  function move(x, y) {
    let res = [];
    const direction = [
      [1, 0],
      [0, 1],
      [-1, 0],
      [0, -1],
    ];

    for (let dir of direction) {
      if (isValid(x + dir[0], y + dir[1])) {
        res.push([x + dir[0], y + dir[1]]);
      }
    }

    return res;
  }

  function isValid(x, y) {
    return x >= 0 && x < N && y >= 0 && y < N;
  }

  function dfs(grid, i, j, color) {
    let area = 0;
    grid[i][j] = color;

    for (let p of move(i, j)) {
      if (grid[p[0]][p[1]] === 1) {
        area += dfs(grid, p[0], p[1], color);
      }
    }
    return area + 1; // 1 is added for the first grid[i][j] line 14
  }
};
```

###### Time and Space Complexity

Since we iterate through our grid **2** times i.e 2 times **O(N&sup2;)** ,our Time Complexity is **O(N&sup2;)** .
Our Space Complexity is also **O(N&sup2;)** as recursion depth can go upto **N&sup2;**.
