Max Area of Island

Medium · Graphs · Explanation and code example

Disjoint Set Union

How it works

Think of each land cell (1) as a node in a graph.
If two land cells are adjacent (up, down, left, right), they belong to the same island.

Using Disjoint Set Union (Union-Find):

  • Each land cell starts as its own component
  • When two neighboring land cells are found, we union them
  • The size of a connected component represents the area of that island
  • Track the maximum component size

This approach is useful when you want to group connected components efficiently.

Steps

  1. Treat each cell as a unique node using index = r * COLS + c.
  2. Initialize DSU with ROWS * COLS elements.
  3. Traverse the grid:
    • If the current cell is land (1):
      • Check its 4 neighbors.
      • If a neighbor is also land, union the two cells.
  4. After unions, for each land cell:
    • Find the size of its connected component.
    • Update the maximum area.
  5. Return the maximum area found.

Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

Where m is the number of rows and n is the number of columns in the grid.

Things to watch for

Forgetting to Mark Cells as Visited

A common mistake is not marking cells as visited before or immediately after processing them. This leads to infinite recursion in DFS or infinite loops in BFS, as the same cell gets added to the queue or call stack repeatedly. Always mark a cell as visited (either by using a separate visited set or by modifying the grid value to 0) before exploring its neighbors.

Incorrect Boundary Checks

Failing to properly check grid boundaries before accessing grid[r][c] causes index-out-of-bounds errors. The order of conditions matters: always check r >= 0 && r < ROWS && c >= 0 && c < COLS before checking grid[r][c]. Short-circuit evaluation prevents the array access when indices are invalid.

Counting Area Incorrectly in BFS

In BFS, a subtle bug occurs when you increment the area count at the wrong time. The area should be incremented when a cell is added to the queue and marked as visited, not when it is dequeued. If you increment when dequeuing, you may count the same cell multiple times if it gets added to the queue from different neighbors before being processed.

Python code example

from typing import List

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n + 1))
        self.Size = [1] * (n + 1)

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] >= self.Size[pv]:
            self.Size[pu] += self.Size[pv]
            self.Parent[pv] = pu
        else:
            self.Size[pv] += self.Size[pu]
            self.Parent[pu] = pv
        return True

    def getSize(self, node):
        par = self.find(node)
        return self.Size[par]

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        dsu = DSU(ROWS * COLS)

        def index(r, c):
            return r * COLS + c

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        area = 0

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1:
                    for dr, dc in directions:
                        nr, nc = r + dr, c + dc
                        if (nr < 0 or nc < 0 or nr >= ROWS or
                            nc >= COLS or grid[nr][nc] == 0
                        ):
                            continue

                        dsu.union(index(r, c), index(nr, nc))

                    area = max(area, dsu.getSize(index(r, c)))

        return area

C++ code example

class DSU {
    vector<int> Parent, Size;
public:
    DSU(int n) {
        Parent.resize(n + 1);
        Size.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            Parent[i] = i;
            Size[i] = 1;
        }
    }

    int find(int node) {
        if (node != Parent[node]) {
            Parent[node] = find(Parent[node]);
        }
        return Parent[node];
    }

    bool unionBySize(int u, int v) {
        int pu = find(u);
        int pv = find(v);
        if (pu == pv) return false;
        if (Size[pu] >= Size[pv]) {
            Size[pu] += Size[pv];
            Parent[pv] = pu;
        } else {
            Size[pv] += Size[pu];
            Parent[pu] = pv;
        }
        return true;
    }

    int getSize(int node) {
        return Size[find(node)];
    }
};

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ROWS = grid.size();
        int COLS = grid[0].size();
        DSU dsu(ROWS * COLS);

        int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int area = 0;

        auto index = [&](int r, int c) {
            return r * COLS + c;
        };

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (grid[r][c] == 1) {
                    for (auto& d : directions) {
                        int nr = r + d[0];
                        int nc = c + d[1];
                        if (nr >= 0 && nc >= 0 && nr < ROWS &&
                            nc < COLS && grid[nr][nc] == 1) {
                            dsu.unionBySize(index(r, c), index(nr, nc));
                        }
                    }
                    area = max(area, dsu.getSize(index(r, c)));
                }
            }
        }

        return area;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations