## Algorithm

Problem Name: 827. Making A Large Island

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

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
function largestIsland(grid) {
const map = new Map() //Key: color, Val: size of island painted of that color
map.set(0, 0) //We won't paint island 0, hence make its size 0, we will use this value later
let n = grid.length
let colorIndex = 2 //0 and 1 is already used in grid, hence we start colorIndex from 2
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] == 1) {
let size = paint(grid, i, j, colorIndex)
map.set(colorIndex, size)
colorIndex++
}
}
}

//If there is no island 0 from grid, res should be the size of islands of first color
//If there is no island 1 from grid, res should be 0
let res = map.get(2) || 0
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 0) {
//We use a set to avoid repeatly adding islands with the same color
const set = new Set()
//If current island is at the boundary, we add 0 to the set, whose value is 0 in the map
set.add(i > 0 ? grid[i - 1][j] : 0)
set.add(i < n - 1 ? grid[i + 1][j] : 0)
set.add(j > 0 ? grid[i][j - 1] : 0)
set.add(j < n - 1 ? grid[i][j + 1] : 0)

let newSize = 1 //We need to count current island as well, hence we init newSize with 1
for (let color of set) newSize += map.get(color)
res = Math.max(res, newSize)
}
}
}
return res
}

//Helper method to paint current island and all its connected neighbors
//Return the size of all painted islands at the end
function paint(grid, i, j, color) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid.length || grid[i][j] != 1) return 0
grid[i][j] = color
return (
1 +
paint(grid, i + 1, j, color) +
paint(grid, i - 1, j, color) +
paint(grid, i, j + 1, color) +
paint(grid, i, j - 1, color)
)
}
``````
Copy The Code &

Input

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

Output

cmd
3

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def largestIsland(self, grid):
def explore(i, j):
dic[(i, j)], count[curr] = curr, count[curr] + 1
if i > 0 and grid[i - 1][j] == 1 and (i - 1, j) not in dic: explore(i - 1, j)
if j > 0 and grid[i][j - 1] == 1 and (i, j - 1) not in dic: explore(i, j - 1)
if i + 1 < len(grid) and grid[i + 1][j] ==1 and (i + 1, j) not in dic: explore(i + 1, j)
if j + 1 < len(grid) and grid[i][j + 1] == 1 and (i, j + 1) not in dic: explore(i, j + 1)
if i > 0 and grid[i - 1][j] == 1 and dic[(i - 1, j)] not in adj: adj.add(dic[(i - 1, j)])
if j > 0 and grid[i][j - 1] == 1 and dic[(i, j - 1)] not in adj: adj.add(dic[(i, j - 1)])
if i + 1 < len(grid) and grid[i + 1][j] ==1 and dic[(i + 1, j)] not in adj: adj.add(dic[(i + 1, j)])
if j + 1 < len(grid) and grid[i][j + 1] == 1 and dic[(i, j + 1)] not in adj: adj.add(dic[(i, j + 1)])
curr, dic, count, res = 0, {}, collections.defaultdict(int), 0
for i in range(len(grid)):
for j in range(len(grid)):
if grid[i][j] == 1 and (i, j) not in dic: curr += 1; explore(i, j)
for i in range(len(grid)):
for j in range(len(grid)):
if grid[i][j] == 1: res = max(res, count[dic[(i, j)]])
else: res = max(res, sum(count[r] for r in neighbours(i, j, set())) + 1)
return res
``````
Copy The Code &

Input

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

Output

cmd
3