Algorithm
Problem Name: 827. Making A Large Island
Problem Link: https://leetcode.com/problems/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 1s.
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.lengthn == grid[i].length1 <= n <= 500grid[i][j]is either0or1.
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[0].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)
)
}
Input
grid = [[1,0],[0,1]]
Output
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)
def neighbours(i, j, adj):
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)])
return adj
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
Input
grid = [[1,0],[0,1]]
Output
3