# Max Area of Island
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/max-area-of-island)
Canonical: https://scaleengineer.com/dsa/problems/max-area-of-island
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Matrix
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Dropbox](https://scaleengineer.com/companies/dropbox), [Intuit](https://scaleengineer.com/companies/intuit), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Snowflake](https://scaleengineer.com/companies/snowflake), [Wise](https://scaleengineer.com/companies/wise), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Disney](https://scaleengineer.com/companies/disney), [Smartsheet](https://scaleengineer.com/companies/smartsheet), [Grubhub](https://scaleengineer.com/companies/grubhub)
---
## Problem
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:**

![](https://assets.glich.co/dsa/max-area-of-island/image0.jpg) 

**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`.

# Approaches
## Brute Force with Redundant Traversals
This approach iterates through every single cell in the grid. If a cell contains a '1', it triggers a completely new search (like DFS or BFS) to find the area of the island that cell belongs to. The key inefficiency here is that it doesn't remember which islands have already been fully explored. It uses a temporary `visited` set for each search, leading to repeated calculations for the same island. For example, if an island has an area of `k`, this method will calculate its area `k` separate times, once starting from each of its `k` cells.
**Time:** O((m * n)^2). For each of the `m*n` cells, we might start a traversal. In the worst case (a grid full of '1's), this traversal could visit all `m*n` cells. This results in a quadratic time complexity. · **Space:** O(m * n). Each traversal requires space for the recursion stack (or an explicit stack/queue) and a `visited` set, both of which can grow to the size of the grid in the worst case.
**Pros:** Conceptually straightforward to devise, though its flaws are significant.
**Cons:** Extremely inefficient due to redundant computations.; Will likely result in a 'Time Limit Exceeded' error on most platforms for non-trivial inputs.
### Explanation
The algorithm proceeds by scanning the entire grid. For every single land cell (`1`) it finds, it initiates a full island area calculation. This calculation is self-contained, meaning it uses its own data structure (e.g., a `boolean[][] visited` array) to keep track of visited cells for that specific calculation. After the area is found, this `visited` information is discarded. Consequently, when the main loop moves to the next land cell, even if it's part of the same island just measured, the process repeats from scratch. This leads to a massive amount of redundant work.

For instance, consider a simple 2x2 island:
```
1 1
1 1
```
1. The algorithm starts at `(0,0)`. It launches a DFS, explores all four cells, and finds the area is 4. `maxArea` becomes 4.
2. The main loop moves to `(0,1)`. It launches another DFS, explores all four cells again, and finds the area is 4.
3. This repeats for `(1,0)` and `(1,1)`. The area of this single island is calculated four times.
### Algorithm
*   Initialize `max_area = 0`.
*   For each cell `(r, c)` in the grid:
    *   If `grid[r][c] == 1`:
        *   Create a new `visited` set, specific to this starting cell.
        *   Start a traversal (like DFS) from `(r, c)` to find the area of the island it belongs to. The traversal function uses the temporary `visited` set to avoid getting stuck in a loop on the current island.
        *   Let the result be `current_area`.
        *   Update `max_area = max(max_area, current_area)`.
*   Return `max_area`.

## Efficient Grid Traversal (DFS or BFS)
This is the optimal approach. We traverse the grid once. When we encounter a land cell ('1') that we haven't visited before, we know we've found a new, unexplored island. We then start a graph traversal (either Depth-First Search or Breadth-First Search) from that cell to find its complete area. A crucial part of this approach is to mark visited land cells (e.g., by changing their value from '1' to '0') to ensure that each island is processed only once. This avoids the redundant computations of the brute-force method.
**Time:** O(m * n), where `m` is the number of rows and `n` is the number of columns. Each cell is visited exactly once by the nested loops, and the traversal (DFS/BFS) also visits each cell within an island exactly once. Therefore, every cell is processed a small, constant number of times. · **Space:** O(m * n) in the worst case. For recursive DFS, this space is used by the call stack (e.g., a long, snake-like island). For iterative BFS/DFS, this space is used by the queue/stack (e.g., if the whole grid is one island).
**Pros:** Optimal time complexity as every cell is processed a constant number of times.; Correctly solves the problem for all cases.; Modifying the grid in-place is space-efficient, avoiding the need for an extra `visited` matrix.
**Cons:** This approach modifies the input grid. If the original grid must be preserved, an auxiliary `visited` matrix of size O(m*n) is needed, which increases the space complexity.
### Explanation
The core idea is to treat the grid as a graph where each '1' is a node and adjacent '1's (horizontally or vertically) have an edge between them. The problem is then equivalent to finding the largest connected component in this graph.

We iterate through every cell of the grid. If we find a cell `(r, c)` with value `1`, we've found a piece of an island that hasn't been counted yet. We then calculate the area of this entire island and update our maximum area found so far. To prevent recounting the same island, once we visit a cell `(r, c)` as part of an island, we 'sink' it by changing its value to `0`. This way, we won't trigger a new search from any other cell belonging to this same island.

We can use either DFS or BFS to explore an island and find its area.

### Using Depth-First Search (DFS) - Recursive
A recursive function explores the island. When it visits a cell, it sinks it and then calls itself for all valid neighbors.
```java
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    maxArea = Math.max(maxArea, dfs(grid, i, j));
                }
            }
        }
        return maxArea;
    }

    private int dfs(int[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0) {
            return 0;
        }
        // Mark as visited by sinking the island part
        grid[r][c] = 0;
        int area = 1;
        area += dfs(grid, r + 1, c);
        area += dfs(grid, r - 1, c);
        area += dfs(grid, r, c + 1);
        area += dfs(grid, r, c - 1);
        return area;
    }
}
```

### Using Breadth-First Search (BFS) - Iterative
An iterative approach using a queue. When a land cell is found, it's added to a queue. The algorithm then processes the queue, exploring the island layer by layer, counting cells and adding new land neighbors to the queue.
```java
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        int m = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int currentArea = 0;
                    Queue<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{i, j});
                    grid[i][j] = 0; // Mark as visited

                    while (!queue.isEmpty()) {
                        int[] cell = queue.poll();
                        int r = cell[0];
                        int c = cell[1];
                        currentArea++;

                        int[] dr = {0, 0, 1, -1};
                        int[] dc = {1, -1, 0, 0};

                        for (int k = 0; k < 4; k++) {
                            int nr = r + dr[k];
                            int nc = c + dc[k];

                            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                                queue.offer(new int[]{nr, nc});
                                grid[nr][nc] = 0; // Mark as visited immediately
                            }
                        }
                    }
                    maxArea = Math.max(maxArea, currentArea);
                }
            }
        }
        return maxArea;
    }
}
```
### Algorithm
*   Initialize `max_area = 0`.
*   Iterate through each cell `(r, c)` of the grid.
*   If `grid[r][c] == 1`:
    *   This cell is part of an uncounted island.
    *   Start a traversal (DFS or BFS) from `(r, c)` to find its area.
    *   The traversal function must:
        1.  Count the current cell.
        2.  Mark the current cell as visited to prevent recounting. A common technique is to 'sink' the island by changing the cell's value from `1` to `0`.
        3.  Recursively or iteratively explore all 4-directional neighbors that are also '1's, adding them to the count and marking them as visited.
    *   Let the total area from the traversal be `current_area`.
    *   Update `max_area = max(max_area, current_area)`.
*   Return `max_area`.

# Solutions
### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  int[][] grid;
public
  int maxAreaOfIsland(int[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans = Math.max(ans, dfs(i, j));
      }
    }
    return ans;
  }
private
  int dfs(int i, int j) {
    if (grid[i][j] == 0) {
      return 0;
    }
    int ans = 1;
    grid[i][j] = 0;
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n) {
        ans += dfs(x, y);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxAreaOfIsland(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int dirs[5] = {-1, 0, 1, 0, -1};
    int ans = 0;
    function<int(int, int)> dfs = [&](int i, int j) {
      if (grid[i][j] == 0) {
        return 0;
      }
      int ans = 1;
      grid[i][j] = 0;
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n) {
          ans += dfs(x, y);
        }
      }
      return ans;
    };
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans = max(ans, dfs(i, j));
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int: def dfs(i: int, j: int) -> int: if grid[i][j] == 0: return 0 ans = 1 grid[i][j] = 0 dirs = (- 1, 0, 1, 0, - 1) for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n: ans += dfs(x, y) return ans m, n = len(grid), len(grid[0]) return max(dfs(i, j) for i in range(m) for j in range(n))

```