695. Max Area of Island - Explanation

Description

You are given a matrix grid where grid[i] is either a 0 (representing water) or 1 (representing land).

An island is defined as a group of 1's connected horizontally or vertically. You may assume all four edges of the grid are surrounded by water.

The area of an island is defined as the number of cells within the island.

Return the maximum area of an island in grid. If no island exists, return 0.

Example 1:

Input: grid = [
  [0,1,1,0,1],
  [1,0,1,0,1],
  [0,1,1,0,1],
  [0,1,0,0,1]
]

Output: 6

Explanation: 1's cannot be connected diagonally, so the maximum area of the island is 6.

Constraints:

1 <= grid.length, grid[i].length <= 50

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the grid.

Hint 1

An island is a group of 1's in which every 1 is reachable from any other 1 in that group. Can you think of an algorithm that can find the number of groups by visiting a group only once? Maybe there is a recursive way of doing it.

Hint 2

We can use the Depth First Search (DFS) algorithm to traverse each group by starting at a cell with 1 and recursively visiting all the cells that are reachable from that cell and are also 1. Can you think about how to find the area of that island? How would you implement this?

Hint 3

We traverse the grid, and when we encounter a 1, we initialize a variable area. We then start a DFS from that cell to visit all connected 1's recursively, marking them as 0 to indicate they are visited. At each recursion step, we increment area. After completing the DFS, we update maxArea, which tracks the maximum area of an island in the grid, if maxArea < area. Finally, after traversing the grid, we return maxArea.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Depth First Search (DFS) - Used to recursively explore all connected land cells in an island
Breadth First Search (BFS) - An alternative traversal using a queue to explore islands level by level
Graph Traversal on Grids - Treating 2D grids as graphs where adjacent cells are connected
Union-Find (Disjoint Set Union) - An advanced technique for grouping connected components efficiently

1. Depth First Search

Intuition

An island is a group of connected 1s.
To find the maximum area, we explore each island fully and count how many cells it contains.

Depth First Search (dfs) helps us:

Start from a land cell
Visit all connected land cells (up, down, left, right)
Count the size of that island
Keep track of the largest size seen

We mark cells as visited so we don't count the same cell twice.

Algorithm

Initialize a visited set to track already counted cells.
For each cell in the grid:
- If it is land (1) and not visited, run dfs from it.
dfs:
- Stop if out of bounds, water (0), or already visited.
- Mark the cell as visited.
- Return 1 + area from all 4 neighbors.
After each dfs call, update the maximum area.
Return the maximum area found.

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

        def dfs(r, c):
            if (r < 0 or r == ROWS or c < 0 or
                c == COLS or grid[r][c] == 0 or
                (r, c) in visit
            ):
                return 0
            visit.add((r, c))
            return (1 + dfs(r + 1, c) +
                        dfs(r - 1, c) +
                        dfs(r, c + 1) +
                        dfs(r, c - 1))

        area = 0
        for r in range(ROWS):
            for c in range(COLS):
                area = max(area, dfs(r, c))
        return area

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

    public int maxAreaOfIsland(int[][] grid) {
        int ROWS = grid.length, COLS = grid[0].length;
        int area = 0;

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (grid[r][c] == 1) {
                    area = Math.max(area, dfs(grid, r, c));
                }
            }
        }

        return area;
    }

    private int dfs(int[][] grid, int r, int c) {
        if (r < 0 || c < 0 || r >= grid.length ||
            c >= grid[0].length || grid[r][c] == 0) {
            return 0;
        }

        grid[r][c] = 0;
        int res = 1;
        for (int[] dir : directions) {
            res += dfs(grid, r + dir[0], c + dir[1]);
        }
        return res;
    }
}

class Solution {
    /**
     * @param {number[][]} grid
     * @return {number}
     */
    maxAreaOfIsland(grid) {
        const directions = [
            [1, 0],
            [-1, 0],
            [0, 1],
            [0, -1],
        ];
        const ROWS = grid.length,
            COLS = grid[0].length;

        const dfs = (r, c) => {
            if (r < 0 || c < 0 || r >= ROWS || c >= COLS || grid[r][c] === 0)
                return 0;

            grid[r][c] = 0;
            let res = 1;
            for (const [dr, dc] of directions) {
                res += dfs(r + dr, c + dc);
            }
            return res;
        };

        let area = 0;
        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                if (grid[r][c] === 1) {
                    area = Math.max(area, dfs(r, c));
                }
            }
        }

        return area;
    }
}

class Solution {
    fun maxAreaOfIsland(grid: Array<IntArray>): Int {
        val rows = grid.size
        val cols = grid[0].size
        val visit = HashSet<Pair<Int, Int>>()

        fun dfs(r: Int, c: Int): Int {
            if (r < 0 || r >= rows || c < 0 || c >= cols ||
                grid[r][c] == 0 || visit.contains(r to c)) {
                return 0
            }
            visit.add(r to c)
            return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
        }

        var area = 0
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                area = maxOf(area, dfs(r, c))
            }
        }
        return area
    }
}

class Solution {
    func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
        let ROWS = grid.count
        let COLS = grid[0].count
        var visit = Set<[Int]>()
        var grid = grid

        func dfs(_ r: Int, _ c: Int) -> Int {
            if (r < 0 || r == ROWS || c < 0 || c == COLS ||
                grid[r][c] == 0 || visit.contains([r, c])) {
                return 0
            }
            visit.insert([r, c])
            return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)
        }

        var area = 0
        for r in 0..<ROWS {
            for c in 0..<COLS {
                area = max(area, dfs(r, c))
            }
        }
        return area
    }
}

impl Solution {
    pub fn max_area_of_island(mut grid: Vec<Vec<i32>>) -> i32 {
        let rows = grid.len();
        let cols = grid[0].len();

        fn dfs(grid: &mut Vec<Vec<i32>>, r: i32, c: i32, rows: i32, cols: i32) -> i32 {
            if r < 0 || r >= rows || c < 0 || c >= cols
                || grid[r as usize][c as usize] == 0
            {
                return 0;
            }
            grid[r as usize][c as usize] = 0;
            1 + dfs(grid, r + 1, c, rows, cols)
                + dfs(grid, r - 1, c, rows, cols)
                + dfs(grid, r, c + 1, rows, cols)
                + dfs(grid, r, c - 1, rows, cols)
        }

        let mut area = 0;
        for r in 0..rows as i32 {
            for c in 0..cols as i32 {
                if grid[r as usize][c as usize] == 1 {
                    area = area.max(dfs(&mut grid, r, c, rows as i32, cols as i32));
                }
            }
        }
        area
    }
}

Time & Space 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$ .

2. Breadth First Search

Intuition

An island is a group of connected 1s.
To find the maximum area, we explore each island completely and count how many cells it has.

Using Breadth First Search (bfs):

Start from a land cell (1)
Visit all connected land cells level by level
Count each visited cell as part of the island
Mark cells as 0 to avoid revisiting
Track the largest island size found

Algorithm

Iterate through every cell in the grid.
When a land cell (1) is found:
- Start bfs from that cell.
- Mark it as visited by setting it to 0.
- Initialize area count to 1.
During bfs:
- Pop a cell from the queue.
- Check its 4 neighbors (up, down, left, right).
- If a neighbor is valid land (1), add it to the queue, mark it 0, and increase area.
After bfs completes, update the maximum area.
Continue scanning the grid.
Return the maximum area found.

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        ROWS, COLS = len(grid), len(grid[0])
        area = 0

        def bfs(r, c):
            q = deque()
            grid[r][c] = 0
            q.append((r, c))
            res = 1

            while q:
                row, col = q.popleft()
                for dr, dc in directions:
                    nr, nc = dr + row, dc + col
                    if (nr < 0 or nc < 0 or nr >= ROWS or
                        nc >= COLS or grid[nr][nc] == 0
                    ):
                        continue
                    q.append((nr, nc))
                    grid[nr][nc] = 0
                    res += 1
            return res

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1:
                    area = max(area, bfs(r, c))

        return area

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

    public int maxAreaOfIsland(int[][] grid) {
        int ROWS = grid.length, COLS = grid[0].length;
        int area = 0;

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (grid[r][c] == 1) {
                    area = Math.max(area, bfs(grid, r, c));
                }
            }
        }

        return area;
    }

    private int bfs(int[][] grid, int r, int c) {
        Queue<int[]> q = new LinkedList<>();
        grid[r][c] = 0;
        q.add(new int[]{r, c});
        int res = 1;

        while (!q.isEmpty()) {
            int[] node = q.poll();
            int row = node[0], col = node[1];

            for (int[] dir : directions) {
                int nr = row + dir[0], nc = col + dir[1];
                if (nr >= 0 && nc >= 0 && nr < grid.length &&
                    nc < grid[0].length && grid[nr][nc] == 1) {
                    q.add(new int[]{nr, nc});
                    grid[nr][nc] = 0;
                    res++;
                }
            }
        }
        return res;
    }
}

class Solution {
    /**
     * @param {number[][]} grid
     * @return {number}
     */
    maxAreaOfIsland(grid) {
        const directions = [
            [1, 0],
            [-1, 0],
            [0, 1],
            [0, -1],
        ];
        const ROWS = grid.length,
            COLS = grid[0].length;
        let area = 0;

        const bfs = (r, c) => {
            const q = new Queue();
            q.push([r, c]);
            grid[r][c] = 0;
            let res = 1;

            while (!q.isEmpty()) {
                const [row, col] = q.pop();
                for (const [dr, dc] of directions) {
                    const nr = row + dr,
                        nc = col + dc;
                    if (
                        nr >= 0 &&
                        nc >= 0 &&
                        nr < ROWS &&
                        nc < COLS &&
                        grid[nr][nc] === 1
                    ) {
                        q.push([nr, nc]);
                        grid[nr][nc] = 0;
                        res++;
                    }
                }
            }
            return res;
        };

        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                if (grid[r][c] === 1) {
                    area = Math.max(area, bfs(r, c));
                }
            }
        }

        return area;
    }
}

class Solution {
    fun maxAreaOfIsland(grid: Array<IntArray>): Int {
        val directions = arrayOf(intArrayOf(1, 0),
                                 intArrayOf(-1, 0),
                                 intArrayOf(0, 1),
                                 intArrayOf(0, -1))
        val rows = grid.size
        val cols = grid[0].size
        var area = 0

        fun bfs(r: Int, c: Int): Int {
            val queue = ArrayDeque<Pair<Int, Int>>()
            grid[r][c] = 0
            queue.add(Pair(r, c))
            var res = 1

            while (queue.isNotEmpty()) {
                val (row, col) = queue.removeFirst()

                for ((dr, dc) in directions) {
                    val nr = dr + row
                    val nc = dc + col

                    if (nr < 0 || nc < 0 || nr >= rows ||
                        nc >= cols || grid[nr][nc] == 0) {
                        continue
                    }

                    queue.add(Pair(nr, nc))
                    grid[nr][nc] = 0
                    res++
                }
            }

            return res
        }

        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (grid[r][c] == 1) {
                    area = maxOf(area, bfs(r, c))
                }
            }
        }

        return area
    }
}

Time & Space 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$ .

3. Disjoint Set Union

Intuition

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.

Algorithm

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

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

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

class DSU {
    constructor(n) {
        this.Parent = Array(n + 1)
            .fill(0)
            .map((_, i) => i);
        this.Size = Array(n + 1).fill(1);
    }

    /**
     * @param {number} node
     * @return {number}
     */
    find(node) {
        if (this.Parent[node] !== node) {
            this.Parent[node] = this.find(this.Parent[node]);
        }
        return this.Parent[node];
    }

    /**
     * @param {number} u
     * @param {number} v
     * @return {boolean}
     */
    union(u, v) {
        let pu = this.find(u);
        let pv = this.find(v);
        if (pu === pv) return false;
        if (this.Size[pu] >= this.Size[pv]) {
            this.Size[pu] += this.Size[pv];
            this.Parent[pv] = pu;
        } else {
            this.Size[pv] += this.Size[pu];
            this.Parent[pu] = pv;
        }
        return true;
    }

    /**
     * @param {number} node
     * @return {number}
     */
    getSize(node) {
        return this.Size[this.find(node)];
    }
}

class Solution {
    /**
     * @param {number[][]} grid
     * @return {number}
     */
    maxAreaOfIsland(grid) {
        const ROWS = grid.length;
        const COLS = grid[0].length;
        const dsu = new DSU(ROWS * COLS);

        const directions = [
            [1, 0],
            [-1, 0],
            [0, 1],
            [0, -1],
        ];
        let area = 0;

        const index = (r, c) => r * COLS + c;

        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                if (grid[r][c] === 1) {
                    for (let [dr, dc] of directions) {
                        let nr = r + dr,
                            nc = c + dc;
                        if (
                            nr >= 0 &&
                            nc >= 0 &&
                            nr < ROWS &&
                            nc < COLS &&
                            grid[nr][nc] === 1
                        ) {
                            dsu.union(index(r, c), index(nr, nc));
                        }
                    }
                    area = Math.max(area, dsu.getSize(index(r, c)));
                }
            }
        }

        return area;
    }
}

public class DSU {
    private int[] Parent, Size;

    public DSU(int n) {
        Parent = new int[n + 1];
        Size = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            Parent[i] = i;
            Size[i] = 1;
        }
    }

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

    public bool Union(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;
    }

    public int GetSize(int node) {
        return Size[Find(node)];
    }
}

public class Solution {
    public int MaxAreaOfIsland(int[][] grid) {
        int ROWS = grid.Length;
        int COLS = grid[0].Length;
        DSU dsu = new DSU(ROWS * COLS);

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

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (grid[r][c] == 1) {
                    foreach (var d in 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.Union(r * COLS + c, nr * COLS + nc);
                        }
                    }
                    area = Math.Max(area, dsu.GetSize(r * COLS + c));
                }
            }
        }

        return area;
    }
}

type DSU struct {
    Parent []int
    Size   []int
}

func (dsu *DSU) find(node int) int {
    if dsu.Parent[node] != node {
        dsu.Parent[node] = dsu.find(dsu.Parent[node])
    }
    return dsu.Parent[node]
}

func (dsu *DSU) union(u, v int) bool {
    pu := dsu.find(u)
    pv := dsu.find(v)
    if pu == pv {
        return false
    }
    if dsu.Size[pu] >= dsu.Size[pv] {
        dsu.Size[pu] += dsu.Size[pv]
        dsu.Parent[pv] = pu
    } else {
        dsu.Size[pv] += dsu.Size[pu]
        dsu.Parent[pu] = pv
    }
    return true
}

func (dsu *DSU) getSize(node int) int {
    par := dsu.find(node)
    return dsu.Size[par]
}

func maxAreaOfIsland(grid [][]int) int {
    rows, cols := len(grid), len(grid[0])
    dsu := DSU{
        Parent: make([]int, rows*cols+1),
        Size:   make([]int, rows*cols+1),
    }

    for i := 0; i <= rows*cols; i++ {
        dsu.Parent[i] = i
        dsu.Size[i] = 1
    }

    index := func(r, c int) int {
        return r*cols + c
    }

    directions := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    area := 0

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == 1 {
                for _, dir := range directions {
                    nr, nc := r+dir[0], c+dir[1]
                    if nr < 0 || nc < 0 || nr >= rows ||
                       nc >= cols || grid[nr][nc] == 0 {
                        continue
                    }
                    dsu.union(index(r, c), index(nr, nc))
                }
                area = max(area, dsu.getSize(index(r, c)))
            }
        }
    }
    return area
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class DSU(n: Int) {
    val Parent = IntArray(n + 1) { it }
    val Size = IntArray(n + 1) { 1 }

    fun find(node: Int): Int {
        if (Parent[node] != node) {
            Parent[node] = find(Parent[node])
        }
        return Parent[node]
    }

    fun union(u: Int, v: Int): Boolean {
        val pu = find(u)
        val 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
    }

    fun getSize(node: Int): Int {
        val par = find(node)
        return Size[par]
    }
}

class Solution {
    fun maxAreaOfIsland(grid: Array<IntArray>): Int {
        val rows = grid.size
        val cols = grid[0].size
        val dsu = DSU(rows * cols)

        val index = { r: Int, c: Int -> r * cols + c }

        val directions = arrayOf(
            intArrayOf(1, 0),
            intArrayOf(-1, 0),
            intArrayOf(0, 1),
            intArrayOf(0, -1)
        )
        var area = 0

        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (grid[r][c] == 1) {
                    for (dir in directions) {
                        val nr = r + dir[0]
                        val nc = c + dir[1]
                        if (nr < 0 || nc < 0 || nr >= rows ||
                            nc >= cols || grid[nr][nc] == 0) {
                            continue
                        }
                        dsu.union(index(r, c), index(nr, nc))
                    }
                    area = maxOf(area, dsu.getSize(index(r, c)))
                }
            }
        }
        return area
    }
}

class DSU {
    private var parent: [Int]
    private var size: [Int]

    init(_ n: Int) {
        parent = Array(0...n)
        size = Array(repeating: 1, count: n + 1)
    }

    func find(_ node: Int) -> Int {
        if parent[node] != node {
            parent[node] = find(parent[node])
        }
        return parent[node]
    }

    func union(_ u: Int, _ v: Int) -> Bool {
        let pu = find(u)
        let 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
    }

    func getSize(_ node: Int) -> Int {
        let par = find(node)
        return size[par]
    }
}

class Solution {
    func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
        var grid = grid
        let ROWS = grid.count
        let COLS = grid[0].count
        let dsu = DSU(ROWS * COLS)

        func index(_ r: Int, _ c: Int) -> Int {
            return r * COLS + c
        }

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

        for r in 0..<ROWS {
            for c in 0..<COLS {
                if grid[r][c] == 1 {
                    for dir in directions {
                        let nr = r + dir.0
                        let nc = c + dir.1
                        if nr < 0 || nc < 0 || nr >= ROWS || nc >= COLS || grid[nr][nc] == 0 {
                            continue
                        }
                        dsu.union(index(r, c), index(nr, nc))
                    }
                    area = max(area, dsu.getSize(index(r, c)))
                }
            }
        }

        return area
    }
}

struct DSU {
    parent: Vec<usize>,
    size: Vec<usize>,
}

impl DSU {
    fn new(n: usize) -> Self {
        Self {
            parent: (0..=n).collect(),
            size: vec![1; n + 1],
        }
    }

    fn find(&mut self, node: usize) -> usize {
        if self.parent[node] != node {
            self.parent[node] = self.find(self.parent[node]);
        }
        self.parent[node]
    }

    fn union(&mut self, u: usize, v: usize) -> bool {
        let pu = self.find(u);
        let 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;
        }
        true
    }

    fn get_size(&mut self, node: usize) -> usize {
        let p = self.find(node);
        self.size[p]
    }
}

impl Solution {
    pub fn max_area_of_island(grid: Vec<Vec<i32>>) -> i32 {
        let rows = grid.len();
        let cols = grid[0].len();
        let mut dsu = DSU::new(rows * cols);

        let directions: [(i32, i32); 4] = [(1, 0), (-1, 0), (0, 1), (0, -1)];
        let mut area = 0usize;

        let index = |r: usize, c: usize| r * cols + c;

        for r in 0..rows {
            for c in 0..cols {
                if grid[r][c] == 1 {
                    for &(dr, dc) in &directions {
                        let nr = r as i32 + dr;
                        let nc = c as i32 + dc;
                        if nr < 0 || nc < 0 || nr >= rows as i32
                            || nc >= cols as i32
                            || grid[nr as usize][nc as usize] == 0
                        {
                            continue;
                        }
                        dsu.union(index(r, c), index(nr as usize, nc as usize));
                    }
                    area = area.max(dsu.get_size(index(r, c)));
                }
            }
        }

        area as i32
    }
}

Time & Space 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$ .

Common Pitfalls

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.