695. Max Area of Island

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/max-area-of-island
• topics: 2D Array, DFS

Description

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.

Idea

• DFS

Code

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        N, M = len(grid), len(grid[0])
        directions = [[0,1], [0,-1], [1,0], [-1,0]]
 
        def dfs(i: int, j: int): 
            nonlocal grid
            grid[i][j], total = 0, 1
            for dx, dy in directions:
                if 0 <= (x:=i+dx) < N and 0 <= (y:=j+dy) < M and grid[x][y]: 
                    total += dfs(x, y)
            return total
 
        return max((dfs(i, j) for i in range(N) 
            for j in range(M) if grid[i][j]), default=0)