MAKING A LARGE ISLAND | LEETCODE # 827 | PYTHON SOLUTION
Vložit
- čas přidán 21. 05. 2022
- In this video we are solving another Facebook interview question: Making a Large Island (Leetcode # 827).
This question builds on the foundation set in questions like "Max Area of an Island" and "Number of Islands" where we want to use DFS to do some traversal of a binary matrix. This problem is a little bit trickier and there's some things we need to take care of in order to actually compute the correct solution here and not double count things. - Věda a technologie
The first example isn't an area of 2 though right b/c 4-directionally doesn't mean diagonal?
Thank you very much , this is quite helpful.
Explained very well 🔥🔥
keep it up bro, great job!
Great walk through, thanks!
very good explanation. Thank you
great explanation and solution, thanks :)
Very well explained, I made a lot of mistakes while coding this up!
Yea it's a tricky one for sure
In the problem statement it says 4-directional, why do you keep counting the diagonals to be a part of the island?
Probably just a mistake on my part. Update the code to use it without it, should be the same
Excellent explanation. Only question is in second for loop of both double for loops why use len(grid[m]) when len(grid[0]) also works?
Doesn’t matter, just personal preference. Both are fine
@@crackfaang thank you
This is my version:
class Solution:
def calculate_potential_connection_size(self, i, j,):
indices_of_starting_cells = set()
# up
if i-1 > -1 and self.grid[i-1][j] != 0: # can be switched with checking if it's a tupple
indices_of_starting_cells.add( self.grid[i-1][j])
# right
if j+1 < len(self.grid[i]) and self.grid[i][j+1] != 0: # can be switched with checking if it's a tupple
indices_of_starting_cells.add( self.grid[i][j+1])
# down
if i+1 < len(self.grid) and self.grid[i+1][j] != 0: # can be switched with checking if it's a tupple
indices_of_starting_cells.add( self.grid[i+1][j])
# left
if j-1 > -1 and self.grid[i][j-1] != 0: # can be switched with checking if it's a tupple
indices_of_starting_cells.add( self.grid[i][j-1])
return sum( [self.starting_cell_indices_to_island_size[pair] for pair in indices_of_starting_cells] ) + 1 # because of 0 the we would change to a 1
def get_island_size(self, i, j, start_i, start_j):
size = 0
if self.grid[i][j] == 1:
size += 1
self.grid[i][j] = (start_i,start_j)
if i-1 > -1: # up
size += self.get_island_size(i-1, j, start_i, start_j)
if j+1 < len(self.grid[i]): # right
size +=self.get_island_size(i, j+1, start_i, start_j)
if i+1 < len(self.grid): # down
size +=self.get_island_size(i+1, j, start_i, start_j)
if j-1 > -1: # left
size += self.get_island_size(i, j-1, start_i, start_j)
else: # self.grid[i][j] must be 0
self.surrounding_zeroes.add((i,j))
return size
def largestIsland(self, grid: List[List[int]]) -> int:
self.grid = grid
# print(f"Before : ")
# self.print_grid()
self.surrounding_zeroes = set()
self.starting_cell_indices_to_island_size = dict()
max_area = 1 # because of 0 the we would change to
for i in range(len(self.grid)):
for j in range(len(self.grid[i])):
if self.grid[i][j] == 1:
self.starting_cell_indices_to_island_size[i, j] = self.get_island_size(i,j, start_i=i, start_j=j)
# print(f"{self.starting_cell_indices_to_island_size[i, j] = }")
max_area = max([max_area, self.starting_cell_indices_to_island_size[i, j]])
# print(f"After : ")
# self.print_grid()
for i, j in self.surrounding_zeroes:
if self.grid[i][j] == 0:
# print(f"the 0 at {i}, {j} = {self.calculate_potential_connection_size(i, j)}")
max_area = max([max_area, self.calculate_potential_connection_size(i, j)])
return max_area
Can you post the solution to the code?
Please cover this one:
249. Group Shifted Strings
thanks!:)
Only if you subscribe to the channel 😉
Already subscribed a month ago and notification bell also turned on!😄