max_area_of_island.py

"""
Given an two dimensional binary matrix grid. An island is a group of 1's (representing
land) connected 4-directionally (horizontal or vertical.) You may assume all four edges
of the grid are surrounded by water. The area of an island is the number of cells with
a value 1 in the island. Return the maximum area of an island in a grid. If there is no
island, return 0.
"""

matrix= [
 [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
 [0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0],
 [0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
]


defis_safe(row: int, col: int, rows: int, cols: int) ->bool:
"""
 Checking whether coordinate (row, col) is valid or not.

 >>> is_safe(0, 0, 5, 5)
 True
 >>> is_safe(-1,-1, 5, 5)
 False
 """
return0<=row<rowsand0<=col<cols


defdepth_first_search(row: int, col: int, seen: set, mat: list[list[int]]) ->int:
"""
 Returns the current area of the island

 >>> depth_first_search(0, 0, set(), matrix)
 0
 """
rows=len(mat)
cols=len(mat[0])
ifis_safe(row, col, rows, cols) and (row, col) notinseenandmat[row][col] ==1:
seen.add((row, col))
return (
1
+depth_first_search(row+1, col, seen, mat)
+depth_first_search(row-1, col, seen, mat)
+depth_first_search(row, col+1, seen, mat)
+depth_first_search(row, col-1, seen, mat)
 )
else:
return0


deffind_max_area(mat: list[list[int]]) ->int:
"""
 Finds the area of all islands and returns the maximum area.

 >>> find_max_area(matrix)
 6
 """
seen: set=set()

max_area=0
forrow, lineinenumerate(mat):
forcol, iteminenumerate(line):
ifitem==1and (row, col) notinseen:
# Maximizing the area
max_area=max(max_area, depth_first_search(row, col, seen, mat))
returnmax_area


if__name__=="__main__":
importdoctest

print(find_max_area(matrix)) # Output -> 6

"""
 Explanation:
 We are allowed to move in four directions (horizontal or vertical) so the possible
 in a matrix if we are at x and y position the possible moving are

 Directions are [(x, y+1), (x, y-1), (x+1, y), (x-1, y)] but we need to take care of
 boundary cases as well which are x and y can not be smaller than 0 and greater than
 the number of rows and columns respectively.

 Visualization
 mat = [
 [0,0,A,0,0,0,0,B,0,0,0,0,0],
 [0,0,0,0,0,0,0,B,B,B,0,0,0],
 [0,C,C,0,D,0,0,0,0,0,0,0,0],
 [0,C,0,0,D,D,0,0,E,0,E,0,0],
 [0,C,0,0,D,D,0,0,E,E,E,0,0],
 [0,0,0,0,0,0,0,0,0,0,E,0,0],
 [0,0,0,0,0,0,0,F,F,F,0,0,0],
 [0,0,0,0,0,0,0,F,F,0,0,0,0]
 ]

 For visualization, I have defined the connected island with letters
 by observation, we can see that
 A island is of area 1
 B island is of area 4
 C island is of area 4
 D island is of area 5
 E island is of area 6 and
 F island is of area 5

 it has 6 unique islands of mentioned areas
 and the maximum of all of them is 6 so we return 6.
 """

doctest.testmod()