Skip to content

Instantly share code, notes, and snippets.

@vrat28
Created June 2, 2021 03:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save vrat28/057f826c0e2286fe38d31f7d7de7652f to your computer and use it in GitHub Desktop.
Save vrat28/057f826c0e2286fe38d31f7d7de7652f to your computer and use it in GitHub Desktop.
Max Area Island (DFS+Recursive)
class Solution {
int[][] grid;
boolean[][] seen;
public int area(int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length ||
seen[r][c] || grid[r][c] == 0)
return 0;
seen[r][c] = true;
return (1 + area(r+1, c) + area(r-1, c)
+ area(r, c-1) + area(r, c+1));
}
public int maxAreaOfIsland(int[][] grid) {
this.grid = grid;
seen = new boolean[grid.length][grid[0].length];
int ans = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
ans = Math.max(ans, area(r, c));
}
}
return ans;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment