Sponsored
Sponsored
In this approach, we will use Depth First Search (DFS) to explore the grid. The idea is to iterate over each cell in the grid and apply DFS when we encounter an unvisited cell that is a part of an island (i.e., grid value is 1). We will mark each visited cell to avoid revisiting. By keeping a count of the size of each island found, we can track the maximum size encountered.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is visited once.
Space Complexity: O(m * n), used for the visited matrix and recursion stack.
1class Solution {
2 private int dfs(int[][] grid, int i, int j) {
3 if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
4 return 0;
5 }
6 grid[i][j] = 0; // Mark as visited
7 return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j)
8 + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
9 }
10
11 public int maxAreaOfIsland(int[][] grid) {
12 int maxArea = 0;
13 for (int i = 0; i < grid.length; i++) {
14 for (int j = 0; j < grid[0].length; j++) {
15 if (grid[i][j] == 1) {
16 maxArea = Math.max(maxArea, dfs(grid, i, j));
17 }
18 }
19 }
20 return maxArea;
21 }
22}This Java solution also employs a DFS method to explore the grid. Each island is marked visited by setting its cells to 0. The maximum area encountered is updated as the grid is traversed.
A Breadth First Search (BFS) approach can also be used to solve this problem by iteratively exploring each cell's neighbors using a queue and counting the size of islands found. By enqueueing all land cell neighbors for exploration and tracking maximum sizes found, we can also determine the maximum island area.
Time Complexity: O(m * n), since all cells are enqueued and dequeued once.
Space Complexity: O(m * n), required for the queue and the visited matrix.
1#include <queue>
#include <algorithm>
class Solution {
public:
int bfs(std::vector<std::vector<int>>& grid, int i, int j) {
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
std::queue<std::pair<int, int>> q;
q.push({i, j});
grid[i][j] = 0; // Mark as visited
int area = 0;
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
area++;
for (auto& dir : directions) {
int newX = x + dir[0], newY = y + dir[1];
if (newX >= 0 && newX < grid.size() && newY >= 0 && newY < grid[0].size() && grid[newX][newY] == 1) {
q.push({newX, newY});
grid[newX][newY] = 0;
}
}
}
return area;
}
int maxAreaOfIsland(std::vector<std::vector<int>>& grid) {
int max_area = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == 1) {
max_area = std::max(max_area, bfs(grid, i, j));
}
}
}
return max_area;
}
};This C++ BFS solution uses a queue to find and measure the area of each island. The cells are marked as visited during the processing, ensuring each is considered only once.