Max Area of Island

Med

#0649Time: 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.11 companies

Algorithms

Depth-First Search Breadth-First Search Union Find

Data structures

Array Matrix

Companies

DoorDash Dropbox Intuit LinkedIn

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

11 121 1

The algorithm starts at (0,0). It launches a DFS, explores all four cells, and finds the area is 4. maxArea becomes 4.
The main loop moves to (0,1). It launches another DFS, explores all four cells again, and finds the area is 4.
This repeats for (1,0) and (1,1). The area of this single island is calculated four times.

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public int maxAreaOfIsland(int[][] grid) {3        int maxArea = 0;4        for (int i = 0; i < grid.length; i++) {5            for (int j = 0; j < grid[0].length; j++) {6                if (grid[i][j] == 1) {7                    maxArea = Math.max(maxArea, dfs(grid, i, j));8                }9            }10        }11        return maxArea;12    }13 14    private int dfs(int[][] grid, int r, int c) {15        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0) {16            return 0;17        }18        // Mark as visited by sinking the island part19        grid[r][c] = 0;20        int area = 1;21        area += dfs(grid, r + 1, c);22        area += dfs(grid, r - 1, c);23        area += dfs(grid, r, c + 1);24        area += dfs(grid, r, c - 1);25        return area;26    }27}

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.

1import java.util.Queue;2import java.util.LinkedList;3 4class Solution {5    public int maxAreaOfIsland(int[][] grid) {6        int maxArea = 0;7        int m = grid.length;8        int n = grid[0].length;9 10        for (int i = 0; i < m; i++) {11            for (int j = 0; j < n; j++) {12                if (grid[i][j] == 1) {13                    int currentArea = 0;14                    Queue<int[]> queue = new LinkedList<>();15                    queue.offer(new int[]{i, j});16                    grid[i][j] = 0; // Mark as visited17 18                    while (!queue.isEmpty()) {19                        int[] cell = queue.poll();20                        int r = cell[0];21                        int c = cell[1];22                        currentArea++;23 24                        int[] dr = {0, 0, 1, -1};25                        int[] dc = {1, -1, 0, 0};26 27                        for (int k = 0; k < 4; k++) {28                            int nr = r + dr[k];29                            int nc = c + dc[k];30 31                            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {32                                queue.offer(new int[]{nr, nc});33                                grid[nr][nc] = 0; // Mark as visited immediately34                            }35                        }36                    }37                    maxArea = Math.max(maxArea, currentArea);38                }39            }40        }41        return maxArea;42    }43}

Complexity

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).

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  int m;4private5  int n;6private7  int[][] grid;8public9  int maxAreaOfIsland(int[][] grid) {10    m = grid.length;11    n = grid[0].length;12    this.grid = grid;13    int ans = 0;14    for (int i = 0; i < m; ++i) {15      for (int j = 0; j < n; ++j) {16        ans = Math.max(ans, dfs(i, j));17      }18    }19    return ans;20  }21private22  int dfs(int i, int j) {23    if (grid[i][j] == 0) {24      return 0;25    }26    int ans = 1;27    grid[i][j] = 0;28    int[] dirs = {-1, 0, 1, 0, -1};29    for (int k = 0; k < 4; ++k) {30      int x = i + dirs[k], y = j + dirs[k + 1];31      if (x >= 0 && x < m && y >= 0 && y < n) {32        ans += dfs(x, y);33      }34    }35    return ans;36  }37}

1class Solution {2public:3  int maxAreaOfIsland(vector<vector<int>> &grid) {4    int m = grid.size(), n = grid[0].size();5    int dirs[5] = {-1, 0, 1, 0, -1};6    int ans = 0;7    function<int(int, int)> dfs = [&](int i, int j) {8      if (grid[i][j] == 0) {9        return 0;10      }11      int ans = 1;12      grid[i][j] = 0;13      for (int k = 0; k < 4; ++k) {14        int x = i + dirs[k], y = j + dirs[k + 1];15        if (x >= 0 && x < m && y >= 0 && y < n) {16          ans += dfs(x, y);17        }18      }19      return ans;20    };21    for (int i = 0; i < m; ++i) {22      for (int j = 0; j < n; ++j) {23        ans = max(ans, dfs(i, j));24      }25    }26    return ans;27  }28};

1class Solution:2    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))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem