A mapping service reports the largest land mass on a binary raster: 1 is land, 0 is water. The intern nested a neighbor walk from every land cell and never marked a cell. An 8×8 fixture in staging hung: two adjacent 1s bounced forever. They added a local seen set but still restarted a full flood from every land cell, then took the max of those sizes. Staging returned in milliseconds. A million-cell continent in production was still flooding when the request timed out.

Max Area of Island asks for the size of the largest 4-connected land blob. Same flood as Number of Islands; that writeup counts starts, this one counts cells. This is an interview writeup, not a layout lecture. The graphs post owns the layout; the DFS post owns the walk. Here we only care about four neighbor deltas, marking land we have already flooded, and keeping the largest component size.

The problem

Given an int[][] grid of 1 (land) and 0 (water), return the area of the largest island — how many cells sit in the biggest 4-connected land blob. Two land cells are the same island when you can walk four directions — up, down, left, right — not diagonals. All water is 0; you may mutate the grid.

0 0 1 0 0
1 1 1 0 0
0 1 0 0 1
0 0 0 1 1     →  5

1 1
1 0           →  3

0 0
0 0           →  0

Note: Off-board is water. Bounds-check first, then skip 0. A 4-direction int[][] dirs table is the neighbor list; do not special-case four ifs unless the board asks you to name them. Number of Islands is the same 4-dir flood on a char[][] of '1'/'0' — that writeup counts starts; this one sizes an int[][] of 1/0.

Restarting a flood from every land cell is the honest brute force

A neighbor walk with no mark never returns. From a 1, step to a neighbor 1, step back, repeat. Staging’s hang was that bounce.

The honest version marks inside one flood so the walk terminates, throws the marks away, and starts again from the next land cell — the size of that cell-set is one island’s area; keep the max. Correct. Quadratic.

int maxAreaRestart(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int max = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) {
                Set<Integer> cells = new HashSet<>();
                collect(grid, r, c, dirs, cells);
                max = Math.max(max, cells.size());
            }
        }
    }
    return max;
}

void collect(int[][] grid, int r, int c, int[][] dirs, Set<Integer> cells) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) {
        return;
    }
    if (grid[r][c] != 1 || !cells.add(r * grid[0].length + c)) {
        return;
    }
    for (int[] d : dirs) {
        collect(grid, r + d[0], c + d[1], dirs, cells);
    }
}

At an 8×8 fixture this is a rounding error. On one island of V land cells you restart a V-cell flood V times: you paid a full walk per land cell for a question that only needs one walk per island.

Count cells, then sink the component

Scan row-major. Every time the cell is still 1, flood it and keep the size — the flood writes 1 → 0 so a later scan cannot start the same blob again. The return is the running max, not a start count.

1 1 0
1 0 1

scan (0,0) land
  flood counts 3, sinks (0,0), (0,1), (1,0)   max=3
scan (0,1) already 0
scan (0,2) water
scan (1,0) already 0
scan (1,1) water
scan (1,2) land
  flood counts 1, sinks (1,2)                 max=3

Four deltas, bounds-check, skip water. Mutation is allowed, so skip a second boolean[][]. The Java is that walk; the flood returns how many cells it sank.

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

int flood(int[][] grid, int r, int c, int[][] dirs) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != 1) {
        return 0;
    }
    grid[r][c] = 0;
    int area = 1;
    for (int[] d : dirs) {
        area += flood(grid, r + d[0], c + d[1], dirs);
    }
    return area;
}

Time is O(mn) — each cell is sunk at most once, and each sunk cell looks at four neighbors. Space is O(mn) for the call stack on a solid island. A million-cell island is a million frames; an iterative ArrayDeque is the same bound without blowing the JVM stack.

Note: Count the cell you just sank. Sink first and forget the + 1, and every island reports 0. Count and forget to sink, and every remaining 1 of the same blob is another start — or a bounce, if you also skipped the mark.

What interviewers usually poke next

  • Iterative flood. Same sink, an ArrayDeque of cells, increment a local area as you pop. BFS (offer / poll) or explicit DFS (push / pop). Not java.util.Stack. Not ArrayList.remove(0).
  • Number of Islands. Count starts, not cells. Same walk, different return.
  • Flood Fill. Recolor one connected component from a seed. Same four deltas and a mark; the seed is given, the size is not.
  • Number of Provinces. Cities and an n × n connection matrix, not a raster. Same idea: start a flood, mark the component — count starts, not area.

You are done with this problem when you can say, out loud, why an unmarked neighbor walk never returns, why restarting a flood from every land cell is quadratic, and why sinking (or a persistent seen) lets you size each island in one pass.