0695. Max Area of Island

0695. 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.

Examples#

Example 1:

Input: grid = [[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]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:#

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1.

Analysis#

  • how to calculate area? -> each land cell will contribute 1 to the area of that island.

  • how to get an island? -> find a starting node, and use DFS/BFS to get the whole land cells for that island

  • Flow:

    • repeatly do:

      • traverse each cell

      • see a land cell

      • calculate the number of its adjacent land cells

      • record the maximum area of island found so far

Solution#

"""A solution using DFS"""
def solution(grid):
    max_area = 0
    R, C = len(grid), len(grid[0])

    seen = [()]

    def dfs(grid, r, c, area, seen):
        # if it is a land cell
        if grid[r][c] == 1:
            # mark it as explored land
            seen.append((r, c))
            area += 1

            # 
            if r > 0 and (r-1, c) not in seen:
                area, seen = dfs(grid, r-1, c, area, seen)
            if r < R - 1 and (r+1, c) not in seen:
                area, seen = dfs(grid, r+1, c, area, seen)
            if c > 0 and (r, c-1) not in seen:
                area, seen = dfs(grid, r, c-1, area, seen)
            if c < C - 1 and (r, c+1) not in seen:
                area, seen = dfs(grid, r, c+1, area, seen)

        return area, seen

    for r in range(R):
        for c in range(C):
            # if explored already
            if (r, c) in seen:
                continue

            # find an island
            area = 0
            if grid[r][c] == 1:
               area, seen = dfs(grid, r, c, area, seen)

            max_area = max(max_area, area)

    return max_area

# tests
grid = [[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]]
print(solution(grid))

grid = [[0,0,0,0,0,0,0,0]]
print(solution(grid))

6
0

# A precise implementation from Leetcode
# The logic is the same but more beautiful code
def solution(grid):
    seen = set()
    def area(r, c):
        if not (0 <= r < len(grid) and 0 <= c < len(grid[0])
                and (r, c) not in seen and grid[r][c]):
            return 0
        seen.add((r, c))
        return (1 + area(r+1, c) + area(r-1, c) +
                area(r, c-1) + area(r, c+1))

    return max(area(r, c)
                for r in range(len(grid))
                for c in range(len(grid[0])))

# tests
grid = [[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]]
print(solution(grid))

grid = [[0,0,0,0,0,0,0,0]]
print(solution(grid))

6
0
Contents