82.Max Area of Island

MediumGraphs · 3/19

Problem

You are given an m x n binary matrix grid, where 1 is land and 0 is water. An island is a group of 1s connected 4-directionally (up, down, left, right). The area of an island is the number of cells in it.

Return the maximum area of any island in grid. If there is no island, return 0.

Examples

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 island in columns 8–10 of rows 3–5 has 6 cells. Diagonal cells do not connect, so it is not bigger.

Input:  grid = [[0,0,0,0,0,0,0,0]]
Output: 0
Explanation: There is no land.

Input:  grid = [
  [1,1,0],
  [1,0,0],
  [0,1,1]
]
Output: 3
Explanation: Top-left island has area 3, bottom-right island has area 2.

Constraints

m == grid.length, n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1

💡 Key Insight

This is Number of Islands with one extra number per island: instead of just counting components, measure each one. A flood fill (DFS or BFS) started from an unvisited land cell visits exactly the cells of that island, so returning 1 + area(neighbours) gives its size. Mark cells as you visit them so every cell contributes to exactly one island, giving O(m·n) total.

Brute Force

TimeO((m·n)²)SpaceO(m·n)

Intuition

For every land cell, run a fresh BFS with its own visited array and count how many cells it reaches. That count is the area of the island containing this cell, so the maximum over all cells is the answer. Every cell of an island recomputes the same area, which is wasted work.

Algorithm

For every cell (r, c) with grid[r][c] == 1:
- BFS from (r, c) using a new visited array; count reached cells as area.
- best = max(best, area).
Return best.

Visualization

grid
1 1 0
1 0 0
0 1 1

(0,0): BFS reaches (0,0),(0,1),(1,0) → area 3   best = 3
(0,1): BFS reaches the same 3 cells  → area 3   (repeated work)
(1,0): area 3                                    (repeated work)
(2,1): BFS reaches (2,1),(2,2)       → area 2
(2,2): area 2
answer = 3

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int maxAreaOfIsland(int[][] grid) {
        int best = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == 1) {
                    best = Math.max(best, islandSize(grid, r, c));
                }
            }
        }
        return best;
    }

    // Fresh BFS from (r, c), counting every reachable land cell
    private int islandSize(int[][] grid, int r, int c) {
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{r, c});
        visited[r][c] = true;
        int area = 0;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            area++;
            for (int[] d : DIRS) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && !visited[nr][nc] && grid[nr][nc] == 1) {
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        return area;
    }
}

Complexity

Time: O((m·n)²) — up to m·n land cells, each running a BFS (and allocating a visited array) of size up to m·n.
Space: O(m·n) — visited and the queue for one BFS.

Union-Find with Sizes

TimeO(m·n·α(m·n))SpaceO(m·n)

Intuition

Give every land cell its own set of size 1. Union each land cell with its land neighbour to the right and below. When two different sets merge, the new root's size is the sum of both sizes. Track the largest size seen at any moment — that is the biggest island.

Algorithm

For each land cell id = r * cols + c: parent[id] = id, size[id] = 1, and best = 1.
For each land cell, union it with the right / down neighbour if that neighbour is land.
In union, attach the smaller set under the larger, add sizes, and update best.
Return best (0 if there was no land).

Dry Run

grid      ids
1 1 0     0 1 2
1 0 0     3 4 5
0 1 1     6 7 8

init: sets {0}{1}{3}{7}{8}, best = 1
cell 0: union(0,1) → {0,1} size 2,   best = 2
cell 0: union(0,3) → {0,1,3} size 3, best = 3
cell 7: union(7,8) → {7,8} size 2,   best = 3
answer = 3

flowchart LR
    A["{0} {1} {3} {7} {8}<br/>best = 1"] -->|"union(0,1)"| B["{0,1}=2<br/>best = 2"]
    B -->|"union(0,3)"| C["{0,1,3}=3<br/>best = 3"]
    C -->|"union(7,8)"| D["{7,8}=2<br/>best = 3"]
    D --> E["return 3"]

Code

java

class Solution {
    private int[] parent;
    private int[] size;
    private int best;

    public int maxAreaOfIsland(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        parent = new int[rows * cols];
        size = new int[rows * cols];
        best = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    int id = r * cols + c;
                    parent[id] = id;
                    size[id] = 1;
                    best = 1; // at least one island of area 1
                }
            }
        }

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != 1) continue;
                int id = r * cols + c;
                if (r + 1 < rows && grid[r + 1][c] == 1) union(id, id + cols);
                if (c + 1 < cols && grid[r][c + 1] == 1) union(id, id + 1);
            }
        }
        return best;
    }

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    }

    private void union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return;
        if (size[ra] < size[rb]) {
            int tmp = ra; ra = rb; rb = tmp;
        }
        parent[rb] = ra;            // smaller tree under larger
        size[ra] += size[rb];
        best = Math.max(best, size[ra]);
    }
}

Complexity

Time: O(m·n·α(m·n)) — at most two unions per cell, each nearly O(1).
Space: O(m·n) — parent and size arrays.

DFSOptimal

TimeO(m·n)SpaceO(m·n)

Intuition

Scan the grid; at each unvisited land cell start a DFS that returns the size of its island. The DFS sets each cell it enters to 0 (so it is never counted again) and returns 1 + dfs(down) + dfs(up) + dfs(right) + dfs(left). Water and out-of-bounds cells return 0. Each cell is visited once overall.

Algorithm

For each cell (r, c) with grid[r][c] == 1: best = max(best, dfs(r, c)).
dfs(r, c): if out of bounds or grid[r][c] == 0 return 0.
Set grid[r][c] = 0, then return 1 plus the four recursive calls.
Return best.

Dry Run

flowchart TD
    A["dfs(0,0): mark 0"] --> B["dfs(1,0): mark 0<br/>neighbours all water → 1"]
    A --> C["dfs(0,1): mark 0<br/>neighbours all water → 1"]
    B --> D["dfs(0,0) returns 1 + 1 + 1 = 3"]
    C --> D
    D --> E["best = 3"]
    E --> F["dfs(2,1) → 1 + dfs(2,2) = 2<br/>best stays 3"]

Code

java

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int best = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == 1) {
                    best = Math.max(best, area(grid, r, c));
                }
            }
        }
        return best;
    }

    // Returns the size of the island containing (r, c) and sinks it
    private int area(int[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0) {
            return 0;
        }
        grid[r][c] = 0; // visited
        return 1
                + area(grid, r + 1, c)
                + area(grid, r - 1, c)
                + area(grid, r, c + 1)
                + area(grid, r, c - 1);
    }
}

Complexity

Time: O(m·n) — each cell is sunk once and checked a constant number of times.
Space: O(m·n) — worst-case recursion depth when all 2,500 cells form one winding island.

Complexity Comparison

Approach	Time	Space
Brute Force	O((m·n)²)	O(m·n)
Union-Find with Sizes	O(m·n·α(m·n))	O(m·n)
DFS	O(m·n)	O(m·n)

Common Pitfalls

Returning -1 or throwing when there is no land — the expected answer is 0.
Marking a cell visited after the recursive calls; neighbours then recurse back into it and the area is counted multiple times (or recursion never ends).
Counting diagonal cells as part of the same island.
In Union-Find, updating best with the size of a non-root node — sizes are only valid at roots.
Forgetting that DFS mutates grid; copy it first if the caller needs the original.