# Max Area of Island – LeetCode Solution [Medium]

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.
###### Approach

This question can be solved easily by BFS (Breadth-first search).

We iteratively visit every cell in grid and on visiting a cell, we mark it as visited. So that, we do not count a cell twice. While iterating the grid, we keep updating a variable (ans) to store the largest area, yet discovered.

class Solution {
public:

//We apply BFS on given grid
void solve (vector<vector<int>>& grid,
vector<vector<int>>& vis,
queue<vector<int>>& qu,
int& ans, const int n, const int m) {
int x = 0;
while (!qu.empty()) {
vector<int> cell = qu.front();
qu.pop();

//Checking left cell
if (cell-1>=0 &&
vis[cell-1][cell] == 0 &&
grid[cell-1][cell] == 1) {
vis[cell-1][cell] = 1;
x = grid[cell-1][cell] ==
1 ? (cell+1) : 0;
ans++;
qu.push(vector<int> {x,
cell-1, cell});
}

//Checking top cell
if (cell-1>=0 &&
vis[cell][cell-1] == 0 &&
grid[cell][cell-1] == 1) {
vis[cell][cell-1] = 1;
x = grid[cell][cell-1] ==
1 ? (cell+1) : 0;
ans++;
qu.push(vector<int> {x,
cell, cell-1});
}

//Checking right cell
if (cell+1<n &&
vis[cell+1][cell] == 0 &&
grid[cell+1][cell] == 1) {
vis[cell+1][cell] = 1;
x = grid[cell+1][cell] ==
1 ? (cell+1) : 0;
ans++;
qu.push(vector<int> {x,
cell+1, cell});
}

//Checking bottom cell
if (cell+1<m &&
vis[cell][cell+1] == 0
&& grid[cell][cell+1] == 1) {
vis[cell][cell+1] = 1;
x = grid[cell][cell+1] ==
1 ? (cell+1) : 0;
ans++;
qu.push(vector<int> {x,
cell, cell+1});
}
}
}

int maxAreaOfIsland(vector<vector<int>>& grid) {
queue<vector<int>> qu;
int ans = 0, sol = 0;
const int n = grid.size(), m = grid.size();

//Base case
if (n == 0 || m == 0) {
return 0;
}

//Setting visited vector to 0 (no cell visited)
vector<vector<int>> vis;
for (int i=0; i<n; i++) {
vis.push_back(vector<int> {});
for (int j=0; j<m; j++) {
vis[i].push_back(0);
}
}

//BFS utility loop
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (vis[i][j] == 0 && grid[i][j] == 1){
vector<int> cell;

//marking cell as visited
cell.push_back(1);

//saving cell indices
cell.push_back(i);
cell.push_back(j);
qu.push(cell);
vis[i][j] = 1;
ans = 1;
solve (grid, vis, qu, ans, n, m);
sol = max(sol, ans);
}
}
}
return sol;
}
};