## Algorithm

Problem Name: 695. Max Area of Island

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`.

Example 1: ```Input: grid = [[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],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.
```

Example 2:

```Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0
```

Constraints:

• `m == grid.length`
• `n == grid[i].length`
• `1 <= m, n <= 50`
• `grid[i][j]` is either `0` or `1`.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int maxAreaOfIsland(vector>& grid) {
if(grid.empty()) return 0;
int maxArea = 0, m = grid.size(), n = grid.size();
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(grid[i][j]){
int area = 0;
DFS(grid, i, j, m, n, area, maxArea);
}
return maxArea;
}

void DFS(vector>& grid, int r, int c, int m, int n, int& area, int& maxArea){
if(r < 0 || c < 0 || r == m || c == n || grid[r][c] == 0){
maxArea = max(maxArea, area);
return;
}
area++;
grid[r][c] = 0;
DFS(grid, r + 1, c, m, n, area, maxArea);
DFS(grid, r - 1, c, m, n, area, maxArea);
DFS(grid, r, c + 1, m, n, area, maxArea);
DFS(grid, r, c - 1, m, n, area, maxArea);
}
};
``````
Copy The Code &

Input

cmd
grid = [[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],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]

Output

cmd
6

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
private final int[][] DIRS = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};

public int maxAreaOfIsland(int[][] grid) {
int area = 0;
int rows = grid.length;
int cols = grid.length;
boolean[][] visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
int currArea = 0;
visited[i][j] = true;
while (!queue.isEmpty()) {
int[] removed = queue.remove();
currArea++;
for (int[] dir : DIRS) {
int x = removed + dir;
int y = removed + dir;
if (x >= 0 && y >= 0 && x < rows && y < cols && !visited[x][y] && grid[x][y] == 1) {
visited[x][y] = true;
}
}
}
area = Math.max(area, currArea);
}
}
}
return area;
}
}
``````
Copy The Code &

Input

cmd
grid = [[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],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]

Output

cmd
6

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maxAreaOfIsland = function(grid) {
let res = 0
const seen = []
for(let i = 0; i < grid.length; i++) {
seen[i] = []
}
for(let i = 0; i < grid.length; i++) {
for(let j = 0; j < grid.length; j++) {
res = Math.max(res, area(i, j, seen, grid))
}
}
return res
};

function area(r, c, seen, grid) {
console.log(grid)
if (r < 0 || r >= grid.length || c < 0 || c >= grid.length || seen[r][c] || grid[r][c] == 0) return 0;
seen[r][c] = true;
return (1 + area(r+1, c, seen, grid) + area(r-1, c, seen, grid) + area(r, c-1, seen, grid) + area(r, c+1, seen, grid));
}

console.log(maxAreaOfIsland([[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]))
console.log(maxAreaOfIsland([[1,0],[1,1]]))
console.log(maxAreaOfIsland([[1,1],[1,0]]))
``````
Copy The Code &

Input

cmd
grid = [[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],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]

Output

cmd
6

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maxAreaOfIsland(self, grid):
m, n = len(grid), len(grid and grid)
def explore(i, j):
grid[i][j] = 0
return 1 + sum(explore(x,y) for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)) if 0<=x``````
``` Copy The Code & Input x – + cmd grid = [[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],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] Output x – + cmd 6 ```
``` #5 Code Example with C# Programming Code - C# Programming using System; namespace LeetCode { public class _0695_MaxAreaOfIsland { public int MaxAreaOfIsland(int[][] grid) { var uf = new UnionFind(grid); int m = grid.Length; int n = grid.Length; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (grid[i][j] == 1) { if (i - 1 >= 0 && grid[i - 1][j] == 1) uf.Union(i * n + j, (i - 1) * n + j); if (i + 1 < m && grid[i + 1][j] == 1) uf.Union(i * n + j, (i + 1) * n + j); if (j - 1 >= 0 && grid[i][j - 1] == 1) uf.Union(i * n + j, i * n + j - 1); if (j + 1 < n && grid[i][j + 1] == 1) uf.Union(i * n + j, i * n + j + 1); } return uf.RankMax(); } public class UnionFind { private int count = 0; private int rankMax = 0; private int[] parents; private int[] ranks; public UnionFind(int[][] grid) { count = 0; int m = grid.Length; int n = grid.Length; parents = new int[m * n]; ranks = new int[m * n]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { parents[i * n + j] = i * n + j; count++; ranks[i * n + j] = 1; rankMax = 1; } } } public int Find(int index) { if (parents[index] != index) parents[index] = Find(parents[index]); return parents[index]; } public void Union(int index1, int index2) { var pIndex1 = Find(index1); var pIndex2 = Find(index2); if (pIndex1 != pIndex2) { if (ranks[pIndex1] >= ranks[pIndex2]) { parents[pIndex2] = pIndex1; ranks[pIndex1] += ranks[pIndex2]; rankMax = Math.Max(ranks[pIndex1], rankMax); } else { parents[pIndex1] = pIndex2; ranks[pIndex2] += ranks[pIndex1]; rankMax = Math.Max(ranks[pIndex2], rankMax); } count--; } } public int RankMax() { return rankMax; } public int Count() { return count; } } } } Copy The Code & Input x – + cmd grid = [[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],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] Output x – + cmd 6 Demonstration ```
``` #693 Leetcode Binary Number with Alternating Bits Solution in C, C++, Java, JavaScript, Python, C# Leetcode #696 Leetcode Count Binary Substrings Solution in C, C++, Java, JavaScript, Python, C# Leetcode ```
``` ```