# 695. Max Area of Island

Given a non-empty 2D array `grid` of 0’s and 1’s, 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.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

``````[[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]]
``````

Given the above grid, return `6`. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

``````[[0,0,0,0,0,0,0,0]]
``````

Given the above grid, return `0`.

Note: The length of each dimension in the given `grid` does not exceed 50.

``````class Solution {
public:
vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), res = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != 1) continue;
int cnt = 0;
helper(grid, i, j, cnt, res);
}
}
return res;
}
void helper(vector<vector<int>>& grid, int i, int j, int& cnt, int& res) {
int m = grid.size(), n = grid[0].size();
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] <= 0) return;
res = max(res, ++cnt);
grid[i][j] *= -1;
for (auto dir : dirs) {
helper(grid, i + dir[0], j + dir[1], cnt, res);
}
}
};
``````

``````class Solution {
public:
vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), res = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != 1) continue;
int cnt = 0;
queue<pair<int, int>> q{{{i, j}}};
grid[i][j] *= -1;
while (!q.empty()) {
auto t = q.front(); q.pop();
res = max(res, ++cnt);
for (auto dir : dirs) {
int x = t.first + dir[0], y = t.second + dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] <= 0) continue;
grid[x][y] *= -1;
q.push({x, y});
}
}
}
}
return res;
}
};
``````

Number of Distinct Islands

Island Perimeter

Number of Islands

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation