imagine you have a grid m x n that represent water and land.
0 is water
1 is land
then the matrix bellow has 2 islands:
0 1 2 3 4 5
0 0,0,0,1,0,0
1 0,0,0,1,0,0
2 0,1,0,0,0,0
to find the island you should traverse in order to find the number for up, down, left right until find the lands together.
so we could use depth first search using recursive calls until find the island, this technique is used for find pattern in grids or graphs.
algorithm:
- run into ROW and each element run into COLUMN.
- find the x, y / r, c
- check if this is visited
- call dfs function if not visited
-
define dfs function stop criteria
- not in borders r, c > 0 and < length of rows and colums
- is visited, check if the coordinate was visited
- check if it is water
- if stop criteria has passed
- mark as visited
- check around if the coord is land and sum all 4 directions with 1, like this:
sum(
dfs x +1, y,
dfs x - 1, y,
dfs x, y + 1,
dfs x, y - 1,
1 # jump of the cat
)
when return the area is the number of island, so you should store and find the max just using max bultin function
the big o is O(m x n)