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.lengthn == grid[i].length1 <= m, n <= 50grid[i][j]is either0or1.
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]-1>=0 &&
vis[cell[1]-1][cell[2]] == 0 &&
grid[cell[1]-1][cell[2]] == 1) {
vis[cell[1]-1][cell[2]] = 1;
x = grid[cell[1]-1][cell[2]] ==
1 ? (cell[0]+1) : 0;
ans++;
qu.push(vector<int> {x,
cell[1]-1, cell[2]});
}
//Checking top cell
if (cell[2]-1>=0 &&
vis[cell[1]][cell[2]-1] == 0 &&
grid[cell[1]][cell[2]-1] == 1) {
vis[cell[1]][cell[2]-1] = 1;
x = grid[cell[1]][cell[2]-1] ==
1 ? (cell[0]+1) : 0;
ans++;
qu.push(vector<int> {x,
cell[1], cell[2]-1});
}
//Checking right cell
if (cell[1]+1<n &&
vis[cell[1]+1][cell[2]] == 0 &&
grid[cell[1]+1][cell[2]] == 1) {
vis[cell[1]+1][cell[2]] = 1;
x = grid[cell[1]+1][cell[2]] ==
1 ? (cell[0]+1) : 0;
ans++;
qu.push(vector<int> {x,
cell[1]+1, cell[2]});
}
//Checking bottom cell
if (cell[2]+1<m &&
vis[cell[1]][cell[2]+1] == 0
&& grid[cell[1]][cell[2]+1] == 1) {
vis[cell[1]][cell[2]+1] = 1;
x = grid[cell[1]][cell[2]+1] ==
1 ? (cell[0]+1) : 0;
ans++;
qu.push(vector<int> {x,
cell[1], cell[2]+1});
}
}
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
queue<vector<int>> qu;
int ans = 0, sol = 0;
const int n = grid.size(), m = grid[0].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;
}
};