Skip to main content

Making A Large Island

Problem Statement

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.

Leetcode Link

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

Python Code

class Solution(object):
def largestIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid or not grid[0]: return 0
# First do a regular union find to find all the islands and their sizes, remember the biggest island's size in 'biggest'.
# Also remember all zero positions
uf={}
size={}
rank={}
zeros=[]
biggest=0
def findparent(x):
if x not in uf: return x
if uf[x]!=x: return findparent(uf[x])
return x
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]==0:
zeros.append((i,j))
continue
if (i,j) not in uf:
uf[(i,j)]=(i,j)
rank[(i,j)]=0
size[(i,j)]=1
biggest=max(biggest,1)
for ni,nj in [(i-1,j),(i,j-1)]:
if 0<=ni<len(grid) and 0<=nj<len(grid[0]) and (ni,nj) in uf:
parA=findparent((i,j))
parB=findparent((ni,nj))
if parA!=parB:
if rank[parA]>rank[parB]:
uf[parB]=parA
rank[parA]+=1
size[parA]+=size[parB]
biggest=max(biggest,size[parA])
else:
uf[parA]=parB
rank[parB]+=1
size[parB]+=size[parA]
biggest=max(biggest,size[parB])
# Now loop over the zeros, and check all of its '1' neighbors, and tally their sizes in 'neisizes'
# If this new '1' connects multiple previously separated islands, the new island's size would be sum(neisizes)+1
for i,j in zeros:
neisizes=[]
visited=set()
for ni,nj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
if 0<=ni<len(grid) and 0<=nj<len(grid[0]) and (ni,nj) in uf:
par=findparent((ni,nj))
if par not in visited:
neisizes.append(size[par])
visited.add(par)
biggest=max(biggest,sum(neisizes)+1)
return biggest