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
This BFS C solution uses a queue to iteratively visit all land cells in a discovered island, marking them visited as they are dequeued. Queue-based exploration ensures that contiguous cells are considered in groups.