[LeetCode] #695: Max Area of Island

Problem:

You are given an m x n 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 grid. If there is no island, return 0.

Time Taken: 15min

---

Process:

Objective: Return the maximum area of an island in grid. If there is no island, return 0.

Constraints:
1. m == grid.length
2. n == grid[i].length
3. 1 <= m, n <= 50
4. grid[i][j] is either 0 or 1.
*From the number of inputs that we are given with, I think it would be fine for us to solve this in quadratic time complexity.

Edge Cases:
1. No island in the grid

Additional Details:
1. If there is no island, return 0

---

Solution:

Approach #1: Iterating through each grid and finding area of each island~~

• Time Complexity: O(nxm)
• Space Complexity: O(nxm)

How it works
1. We will use the exact same algorithm from "Number of Islands" problem: iterating through each grid while traversing to neighboring land to mark them as visited.
2. We modified the recursision function to find the area of each island.

def dfs(self, grid, x, y) -> int:
        area = 0
        if -1 < x < len(grid[0]) and -1 < y < len(grid) and grid[y][x] == 1:
            grid[y][x] = 2
            area = 1
            area += self.dfs(grid, x+1, y) + self.dfs(grid, x-1, y) + self.dfs(grid, x, y+1) + self.dfs(grid, x, y-1)
        
        return area
    
    
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        max_area = 0
        
        for x in range(len(grid[0])):
            for y in range(len(grid)):
                if grid[y][x] == 1:
                    island_area = self.dfs(grid, x, y)
                    if max_area < island_area:
                        max_area = island_area
                    
        return max_area

Limitations:
1. Again, recursion creates a whole lot of call stack which accumulates to our space complexity.

---

Extra Approach: Exactly same, but with modified if statement to short circuit the recursion

This is just a simple modification to return 0 for area by allowing it to short circuit. This havled the time complexity of the original code.

def dfs(self, grid, x, y) -> int:
        area = 0
        if x < 0 or y < 0 or x >= len(grid[0]) or y >= len(grid) or grid[y][x] != 1:
            area = 0
        else:
            grid[y][x] = 2
            area = 1
        
            area += self.dfs(grid, x+1, y) + self.dfs(grid, x-1, y) + self.dfs(grid, x, y+1) + self.dfs(grid, x, y-1)
        
        return area
    
    
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        max_area = 0
        
        for x in range(len(grid[0])):
            for y in range(len(grid)):
                if grid[y][x]:
                    island_area = self.dfs(grid, x, y)
                    if max_area < island_area:
                        max_area = island_area
                    
        return max_area

Limitations:

• The code looks a little verbose.

---

LeetCode Question #695