# [Java/C++] Straightforward dfs solution

• The idea is to count the area of each island using dfs. During the dfs, we set the value of each point in the island to `0`. The time complexity is `O(mn)`.

Java version:

``````    public int maxAreaOfIsland(int[][] grid) {
int max_area = 0;
for(int i = 0; i < grid.length; i++)
for(int j = 0; j < grid[0].length; j++)
if(grid[i][j] == 1)max_area = Math.max(max_area, AreaOfIsland(grid, i, j));
return max_area;
}

public int AreaOfIsland(int[][] grid, int i, int j){
if( i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1){
grid[i][j] = 0;
return 1 + AreaOfIsland(grid, i+1, j) + AreaOfIsland(grid, i-1, j) + AreaOfIsland(grid, i, j-1) + AreaOfIsland(grid, i, j+1);
}
return 0;
}
``````

C++ version:

``````    int maxAreaOfIsland(vector<vector<int>>& grid) {
int max_area = 0;
for(int i = 0; i < grid.size(); i++)
for(int j = 0; j < grid[0].size(); j++)
if(grid[i][j] == 1)max_area = max(max_area, AreaOfIsland(grid, i, j));
return max_area;
}

int AreaOfIsland(vector<vector<int>>& grid, int i, int j){
if( i >= 0 && i < grid.size() && j >= 0 && j < grid[0].size() && grid[i][j] == 1){
grid[i][j] = 0;
return 1 + AreaOfIsland(grid, i+1, j) + AreaOfIsland(grid, i-1, j) + AreaOfIsland(grid, i, j-1) + AreaOfIsland(grid, i, j+1);
}
return 0;
}
``````

• Had same idea but set visited part of island to '-1'so it's easy to debug:

``````class Solution {
int max = 0, maxNow = 0;
public int maxAreaOfIsland(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1){
maxNow = 0;
dfs(i, j, grid);}
}
}
return max;
}

private void dfs(int i, int j, int[][]grid) {
if (i < 0 || j < 0 ||
i >= grid.length || j >= grid[0].length ||
grid[i][j] != 1) return;
grid[i][j] = -1; // marking part of island visited not to check it next time
maxNow++;

dfs(i - 1, j, grid);
dfs(i + 1, j, grid);
dfs(i, j + 1, grid);
dfs(i, j - 1, grid);

max = Math.max(max, maxNow);
}
}
``````

• Worst-case recursion depth will be `O(mn)`, where `m` is the width of the grid and `n` is the height, correct?

So space complexity will be `O(mn)`?

• @FlorenceMachine Yes, the worst space complexity could be `O(mn)`.

• Same idea

``````class Solution {
public int maxAreaOfIsland(int[][] grid) {
int max = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
max = Math.max(max, helper(grid, i, j));
}
}
}
return max;
}
public int helper(int[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
return 0;
}
grid[i][j] = 0;
return 1 + helper(grid, i - 1, j) + helper(grid, i + 1, j) + helper(grid, i, j - 1) + helper(grid, i, j + 1);
}
}
``````

• This post is deleted!

• We may use an extra `visited[][]` so not to modify the input grid.

``````class Solution {
private int I, J;
private int[][] g;
private boolean[][] visited;

private int dfs(int i, int j) {
if (i < 0 || i >= I || j < 0 || j >= J)
return 0;
if (visited[i][j])
return 0;
visited[i][j] = true;
if (g[i][j] == 0)
return 0;
return dfs(i - 1, j) + dfs(i + 1, j) +
dfs(i, j - 1) + dfs(i, j + 1) + 1;
}

public int maxAreaOfIsland(int[][] grid) {
g = grid;
I = g.length;
J = g[0].length;
visited = new boolean[I][J];
int maxArea = 0;
for (int i = 0; i < I; i++)
for (int j = 0; j < J; j++)
if (!visited[i][j] && g[i][j] == 1)
maxArea = Math.max(maxArea, dfs(i, j));
return maxArea;
}
}
``````

• @Vincent-Cai Beautiful solution!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.