LC 0827 [H] Making A Large Island - ALawliet/algorithms GitHub Wiki
prereq: Number of Islands DFS pattern
use colors to track different DFS paths without them interfering with each other and being counted twice
- find the area of each color with a number of islands/DFS approach on the islands and store in hash table that also handles OOB
- write a helper function to get the color of a cell that also handles OOB
- DFS on the gaps and see check merging them with a colored island creates a greater max area color
we count new colors with numbers above 1 so we can use 0 as the initial/empty color
O(n^2)
NO_ISLAND = 0
ISLAND = 1
# COLOR_ISLAND = 1 # > 1
DIRS = [(1,0),(-1,0),(0,1),(0,-1)]
class Solution(object):
def largestIsland(self, grid):
ROWS, COLS = len(grid),len(grid[0])
def dfs(r, c, color):
if 0 <= r < ROWS and 0 <= c < COLS and grid[r][c] == 1:
grid[r][c] = color
return 1 + dfs(r+1,c,color) + dfs(r-1,c,color) + dfs(r,c+1,color) + dfs(r,c-1,color)
else:
return 0
color_to_area = {}
color = 1
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 1: # color islands
color += 1
color_to_area[color] = dfs(r, c, color)
color_to_area[0] = 0 # edge case prevent no values empty sequence like [0,0],[0,0](/ALawliet/algorithms/wiki/0,0],[0,0)
max_area = max(color_to_area.values())
def get_color(r, c):
if 0 <= r < ROWS and 0 <= c < COLS and grid[r][c] > 1:
return grid[r][c]
else:
return 0
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 0: # swappable
color_set = set([ # we use a set cause we could have the same color in multiple directions
get_color(r+1,c),
get_color(r-1,c),
get_color(r,c+1),
get_color(r,c-1)
])
max_area = max(max_area, 1 + sum([color_to_area[color] for color in color_set]))
return max_area
NO_ISLAND = 0
ISLAND = 1
# COLOR_ISLAND = 1 # > 1
DIRS = [(1,0),(-1,0),(0,1),(0,-1)]
class Solution(object):
def largestIsland(self, grid):
n_rows, n_cols = len(grid),len(grid[0])
# dfs to get area and set color
def dfs(r, c, color):
if 0 <= r < n_rows and 0 <= c < n_cols and grid[r][c] == 1:
grid[r][c] = color # fill color
area = 0
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
area += dfs(nr, nc, color)
return area + 1 # + the current cell
# return 1 + dfs(r+1,c,color) + dfs(r-1,c,color) + dfs(r,c+1,color) + dfs(r,c-1,color) # append area
else:
return 0
# tag all islands with different color
color_to_area = {}
color = 1 # why do we start at 1? because 1 means it's an island, so > 1 means its color was set
for r in range(n_rows):
for c in range(n_cols):
if grid[r][c] == 1:
color += 1 # then immediately tag 2?
color_to_area[color] = dfs(r, c, color)
# check all cell == 0 that was not colored
# handle [0,0],[0,0](/ALawliet/algorithms/wiki/0,0],[0,0)
if not color_to_area.values(): return 1
# color_to_area[0] = 0
max_area = max(color_to_area.values())
def get_color(r, c):
if 0 <= r < n_rows and 0 <= c < n_cols and grid[r][c] > 1:
return grid[r][c]
else:
return 0
for r in range(n_rows):
for c in range(n_cols):
if grid[r][c] == 0:
# it has to be a set so we don't count multiple paths
color_set = set()
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < n_rows and 0 <= nc < n_cols and grid[nr][nc] > 1: # > 1 not needed but makes sense to merge into colors
color = grid[nr][nc]
color_set.add(color)
# color_set = set([
# get_color(r+1,c),
# get_color(r-1,c),
# get_color(r,c+1),
# get_color(r,c-1)
# ])
# get max area if we swapped to sum the adjacent islands changed at most a 0 to a 1
new_area = 0
for color in color_set:
new_area += color_to_area[color]
new_area = 1 + new_area
if new_area > max_area:
max_area = new_area
# max_area = max(max_area, 1 + sum([color_to_area[color] for color in color_set]))
return max_area