Scale Engineer

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 SearchBreadth-First SearchUnion Find
Data structures
ArrayMatrix
Companies
DoorDashDropboxIntuitLinkedIn

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:

1 11 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.

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.

Solutions

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;  }}

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 →

Next problem