mediumGraphs

Max Area of Island

Find the largest island area in a binary grid. Only horizontal and vertical land neighbors are connected.

LeetCode ↗

Work through the cases

3 examples

Input notation

Rows of a nonempty rectangular matrix, one space-separated row per line.

Expected result

The maximum number of cells in one island, or 0.

Case 1

Input

1 1 0
0 1 0
1 0 1

Expected output

Case 2

Input

0 0

Expected output

Case 3

Input

1 1
1 1

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Area is the count of 4-connected land cells. Each cell is visited at most once. DFS a land cell, set it to 0, and add the four recursive calls. The answer is the maximum over all starts.

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

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.