Max Area of Island

MEDIUM✓ CHIP-TIMEDLC #695 — FULL STATEMENT ↗

The drill: Same connected-land idea as counting islands, but now measure size — return the cell count of the largest connected group of 1s in a 0/1 grid, or 0 if the grid is all water.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

The same 0/1 grid setup as counting islands, but this time the question is size, not count: among every connected group of 1s, find the one with the most cells and report how many cells it contains.

Connectivity is still strictly orthogonal — a cell only joins its island through an up, down, left, or right neighbor, never a diagonal one — and an island can be as small as a single isolated 1.

When the whole grid is water, there's no island to measure, and the expected answer is simply zero rather than any error state.

EX 01

grid = [[0, 0], [0, 0]]

→ 0

ALL WATER

EX 02

grid = [[1]]

→ 1

SINGLE LAND CELL

EX 03

grid = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]

→ 9

FULL 3X3 ISLAND

grid up to a few hundred cells per side
values are exactly 0 or 1
connectivity is 4-directional only
an all-zero grid answers 0, not an error

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Counting islands and measuring the biggest one are almost the same walk — the only new part is that each flood fill needs to report how many cells it covered.

HINT 2 THE STRUCTURE

Have the flood fill return its own size: 1 for the current cell plus whatever its four neighbours' fills return. Track the largest value seen across every start.

HINT 3 ONE STEP FROM THE ANSWER

DFS from every unvisited land cell, summing 1 + the four recursive calls; keep a running max and return 0 the moment you fall off the grid or hit water or an already-visited cell.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE FLOOD TALLYPATTERN · DFS, SINK IN PLACEgrid = [[1,0,0],[1,1,0],[0,1,1]] — snake-shaped island

STEP 1

DFS floods from every unvisited 1, summing 1 plus each direction's own flood — and sinks each cell to 0 the moment it's counted.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/max-area-of-island.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])

        def area(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
                return 0
            grid[r][c] = 0
            return 1 + area(r + 1, c) + area(r - 1, c) + area(r, c + 1) + area(r, c - 1)

        best = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    best = max(best, area(r, c))
        return best

TIME O(ROWS·COLS)SPACE O(1) EXTRA (RECURSION STACK ONLY)PYTHON · RACE PACE · 16 LN

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        visited = [[False] * cols for _ in range(rows)]

        def area(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0 or visited[r][c]:
                return 0
            visited[r][c] = True
            return 1 + area(r + 1, c) + area(r - 1, c) + area(r, c + 1) + area(r, c - 1)

        best = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1 and not visited[r][c]:
                    best = max(best, area(r, c))
        return best

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)PYTHON · TRAINING PACE · 17 LN

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

    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;
        return 1 + area(grid, r + 1, c) + area(grid, r - 1, c) + area(grid, r, c + 1) + area(grid, r, c - 1);
    }
}

TIME O(ROWS·COLS)SPACE O(1) EXTRA (RECURSION STACK ONLY)JAVA · RACE PACE · 19 LN

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

    private int area(int[][] grid, boolean[][] visited, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0 || visited[r][c]) return 0;
        visited[r][c] = true;
        return 1 + area(grid, visited, r + 1, c) + area(grid, visited, r - 1, c)
                 + area(grid, visited, r, c + 1) + area(grid, visited, r, c - 1);
    }
}

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)JAVA · TRAINING PACE · 22 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED