Max Area of Island — DFS with Area Count

Problem

Return the maximum area of an island (connected 1s) in grid. An island's area is the number of 1-cells.

Example:

Input: [[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],
         ...
Output: 6

Approach — DFS Returns Area

DFS recurses into all 4 neighbours, sums up 1 + area of each subtree. Track global max.

Time: O(mn) | Space: O(mn)

Solutions

C

int dfs(int** g, int r, int c, int R, int C) {
    if(r<0||r>=R||c<0||c>=C||g[r][c]!=1) return 0;
    g[r][c]=0;
    return 1+dfs(g,r+1,c,R,C)+dfs(g,r-1,c,R,C)+dfs(g,r,c+1,R,C)+dfs(g,r,c-1,R,C);
}
int maxAreaOfIsland(int** g, int R, int* cols) {
    int C=cols[0],best=0;
    for(int r=0;r<R;r++) for(int c=0;c<C;c++)
        if(g[r][c]==1) best=fmax(best,dfs(g,r,c,R,C));
    return best;
}

C++

class Solution {
    int dfs(vector<vector<int>>& g, int r, int c) {
        if(r<0||r>=g.size()||c<0||c>=g[0].size()||g[r][c]!=1) return 0;
        g[r][c]=0;
        return 1+dfs(g,r+1,c)+dfs(g,r-1,c)+dfs(g,r,c+1)+dfs(g,r,c-1);
    }
public:
    int maxAreaOfIsland(vector<vector<int>>& g) {
        int best=0;
        for(int r=0;r<g.size();r++) for(int c=0;c<g[0].size();c++)
            if(g[r][c]==1) best=max(best,dfs(g,r,c));
        return best;
    }
};

Java

class Solution {
    private int dfs(int[][] g, int r, int c) {
        if(r<0||r>=g.length||c<0||c>=g[0].length||g[r][c]!=1) return 0;
        g[r][c]=0;
        return 1+dfs(g,r+1,c)+dfs(g,r-1,c)+dfs(g,r,c+1)+dfs(g,r,c-1);
    }
    public int maxAreaOfIsland(int[][] g) {
        int best=0;
        for(int r=0;r<g.length;r++) for(int c=0;c<g[0].length;c++)
            if(g[r][c]==1) best=Math.max(best,dfs(g,r,c));
        return best;
    }
}

JavaScript

var maxAreaOfIsland = function(grid) {
    const dfs=(r,c)=>{
        if(r<0||r>=grid.length||c<0||c>=grid[0].length||grid[r][c]!==1) return 0;
        grid[r][c]=0;
        return 1+dfs(r+1,c)+dfs(r-1,c)+dfs(r,c+1)+dfs(r,c-1);
    };
    let best=0;
    for(let r=0;r<grid.length;r++) for(let c=0;c<grid[0].length;c++)
        if(grid[r][c]===1) best=Math.max(best,dfs(r,c));
    return best;
};

Python

class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        R,C=len(grid),len(grid[0])
        def dfs(r,c):
            if not(0<=r<R and 0<=c<C) or grid[r][c]!=1: return 0
            grid[r][c]=0
            return 1+dfs(r+1,c)+dfs(r-1,c)+dfs(r,c+1)+dfs(r,c-1)
        return max((dfs(r,c) for r in range(R) for c in range(C) if grid[r][c]==1), default=0)

Complexity

Time: O(mn) | Space: O(mn)