#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/graphs-dfs/max-area-of-island-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/graphs-dfs/max-area-of-island-implementation

Repovive

LeetCode 695 Max Area of Island - Implementation - Graphs - DFS | Pattern 22: LeetCode Interview Patterns | Repovive

Repovive.

Pattern 22: LeetCode Interview Patterns24 sections · 736 units32h total

Open in Course

LeetCode 695 Max Area of Island - Implementation

The approach

DFS returns area of island. Track maximum.

function maxAreaOfIsland(grid): m, n = len(grid), len(grid[0]) maxArea = 0

def dfs(r, c):
    if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0:
        return 0
    grid[r][c] = 0
    return 1 + dfs(r-1,c) + dfs(r+1,c) + dfs(r,c-1) + dfs(r,c+1)

for i in range(m):
    for j in range(n):
        if grid[i][j] == 1:
            maxArea = max(maxArea, dfs(i, j))
return maxArea

$O(m \cdot n)$ time.