Max Area of Island

Max Area of Island

• In order to “explore” an island, we need recursion! Recursively explore the four directions.
• We need to keep track of the lands we have traversed.
  • In [[python|Python], it’s easier to use dictionary.
  • In [[c|C], use array instead.

What we could learn from here:

• To get good understanding of a field, of a place, a potential strategy is to recursively traverse it.
• To spend our time wisely, we need to reflect frequently, keep track of what we have done and seen.

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        def area(x, y):
            if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[x]):
                return 0
            if not grid[x][y] or seen[x][y]: return 0
 
            seen[x][y] = 1;
            area_l = area(x, y - 1);
            area_r = area(x, y + 1);
            area_u = area(x - 1, y);
            area_d = area(x + 1, y);
            return 1 + area_l + area_r + area_u + area_d
 
        maxArea = 0
        seen = [[0] * len(grid[i]) for i in range(len(grid))]
 
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                curArea = area(i, j)
                if maxArea < curArea: maxArea = curArea
 
        return maxArea

You can’t even deal with 2D array in C…