Max Area of Island

The problem

You are given grid, a rectangle of cells in which 1 is land and 0 is water. An island is a group of one or more land cells joined side by side: up, down, left or right. Cells that touch only at a corner are not joined. The area of an island is the number of its cells. Return the largest area of any island, or 0 if the grid has no land.

What to write

function solve(grid: number[][]): number

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

Output
4

Input
grid = [[0,0]]

Output
0

Constraints

Land is 1 and water is 0; the grid is rectangular.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Every land cell belongs to exactly one island, so the areas of all the islands add up to the number of 1s in the grid. The answer is 0 only when the grid has no land at all. Cells that touch only at a corner do not make an island larger.

2. Hint 2: Ask a smaller question

   In the first example, start on the 1 in the top row, second column. Which cells can you step to from there, and from those? Now count the cells you visited. What stops you from counting the starting cell again when a neighbor leads back to it?

3. Hint 3: Name the pattern

   An island is a connected component of the grid: a group of cells in which you can walk from any cell to any other. As in Number of Islands, find each group by spreading from its first cell and sinking (writing 0 into) what you reach, and count the cells as you go. The pattern is grid connected components. Read the lesson on grid connected components.

4. Hint 4: State the invariant

   While an island is being walked, the area counted so far equals the number of cells taken off the list. A cell is sunk when it joins the list, so it joins once, is taken off once and is counted once.

5. Hint 5: Sketch the pseudocode

   best = 0. For each cell holding 1: write 0 into it, put it on a list, area = 0. Until the list is empty: take a cell off, add 1 to area, and for each of its four neighbors inside the grid holding 1, write 0 there and add it to the list. best = max(best, area). Return best.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Flood-fill each unvisited island, counting its cells and tracking the largest count.

The slow way

Counting all the 1s gives the total land, not the largest island: the first example would give 5. To measure islands one at a time you could start a walk from every land cell and count the cells the walk reaches. That is correct, but an island of k cells is then measured k times, about k × k steps for that island.

The insight

An island's area is the number of cells you meet while walking over it, provided each cell is met once. Sinking a cell as soon as you find it, which means writing 0 into it, guarantees that. It also removes the island from the grid, so the scan never measures the same island again. One walk per island is enough.

Step by step

1. Keep the largest area found so far, starting at 0. The answer is a maximum over all islands, and 0 is the right answer when the grid has no land, so that is the starting value.
2. Scan every cell, skipping water and land that is already sunk. An island can begin anywhere, so every cell is looked at. A cell that holds 0 is water, or land of an island that was already measured.
3. Land that is still 1 starts a new island: sink it and list it. Sinking means writing 0 into the cell. The list holds cells that are sunk but not yet counted. Starting it with this cell is what lets the walk find the rest.
4. Count the island's cells: add 1 for each cell taken off the list. Every cell of the island passes through the list exactly once, so counting the cells as they leave it gives the area. The count restarts at 0 for each island.
5. Sink each land neighbor of that cell and add it to the list. A land neighbor above, below, left or right belongs to the same island. It is sunk the moment it joins the list, so a second neighbor cannot add it again.
6. The list is empty: keep this area if it is the largest so far. An empty list means every cell of this island has been counted. Its area is final and can be compared with the best one so far.
7. Return the largest area found. Every island was measured once during the scan, so the largest value kept is the answer. With no land it is still the starting 0.

The same numbered steps are the comments in each solution.

function solve(grid) {
  // 1. Keep the largest area found so far, starting at 0
  let best = 0;
  // 2. Scan every cell, skipping water and land that is already sunk
  for (let r = 0; r < grid.length; r++)
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] !== 1) continue;
      // 3. Land that is still 1 starts a new island: sink it and list it
      const stack = [[r, c]];
      grid[r][c] = 0;
      // 4. Count the island's cells: add 1 for each cell taken off the list
      let area = 0;
      while (stack.length) {
        const [x, y] = stack.pop();
        area++;
        // 5. Sink each land neighbor of that cell and add it to the list
        for (const [a, b] of [
          [x + 1, y],
          [x - 1, y],
          [x, y + 1],
          [x, y - 1],
        ])
          // Outside the grid, grid[a]?.[b] is undefined instead of an error,
          // so a neighbor that does not exist is never taken for land.
          if (grid[a]?.[b] === 1) {
            grid[a][b] = 0;
            stack.push([a, b]);
          }
      }
      // 6. The list is empty: keep this area if it is the largest so far
      best = Math.max(best, area);
    }
  // 7. Return the largest area found
  return best;
}

function solve(grid: number[][]): number {
  // 1. Keep the largest area found so far, starting at 0
  let best = 0;
  // 2. Scan every cell, skipping water and land that is already sunk
  for (let r = 0; r < grid.length; r++)
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] !== 1) continue;
      // 3. Land that is still 1 starts a new island: sink it and list it
      const stack = [[r, c]];
      grid[r][c] = 0;
      // 4. Count the island's cells: add 1 for each cell taken off the list
      let area = 0;
      while (stack.length) {
        const [x, y] = stack.pop()!;
        area++;
        // 5. Sink each land neighbor of that cell and add it to the list
        for (const [a, b] of [
          [x + 1, y],
          [x - 1, y],
          [x, y + 1],
          [x, y - 1],
        ])
          // Outside the grid, grid[a]?.[b] is undefined instead of an error,
          // so a neighbor that does not exist is never taken for land.
          if (grid[a]?.[b] === 1) {
            grid[a][b] = 0;
            stack.push([a, b]);
          }
      }
      // 6. The list is empty: keep this area if it is the largest so far
      best = Math.max(best, area);
    }
  // 7. Return the largest area found
  return best;
}

def solve(grid):
    # 1. Keep the largest area found so far, starting at 0
    best = 0
    # 2. Scan every cell, skipping water and land that is already sunk
    rows, cols = len(grid), len(grid[0])
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1:
                continue
            # 3. Land that is still 1 starts a new island: sink it and list it
            stack = [(r, c)]
            grid[r][c] = 0
            # 4. Count the island's cells: add 1 for each cell taken off the list
            area = 0
            while stack:
                x, y = stack.pop()
                area += 1
                # 5. Sink each land neighbor of that cell and add it to the list
                for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                    # A negative index would read from the far edge of the grid,
                    # so the neighbor is first checked to lie inside it.
                    if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                        grid[nx][ny] = 0
                        stack.append((nx, ny))
            # 6. The list is empty: keep this area if it is the largest so far
            best = max(best, area)
    # 7. Return the largest area found
    return best

Example 1, traced

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

Output
4

Why it works

A cell joins the list only when it is sunk, and a sunk cell is never land again, so each cell of an island is listed, taken off and counted exactly once. The walk only moves between neighboring land cells, so it never leaves the island, and it reaches all of it. Each area is therefore exact, and the largest is kept.

Time and space

Time O(rows · cols), extra space O(rows · cols). The grid has rows · cols cells. The scan looks at each once, and a cell is sunk at most once, so it is listed, taken off and counted at most once: O(rows · cols) time. The list never holds more cells than the grid has: O(rows · cols) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Sink a cell when it joins the list, not when it is taken off. Sunk late, a cell can be added by two neighbors and counted twice: a 2 × 2 block of land then gets area 5, not 4.
• Start the area at 0 again for every island. If the count is set to 0 only once, before the scan, the first example adds its two islands together and returns 5 instead of 4.
• In Python, check that a neighbor's row and column are not negative. Row -1 is not an error there but the last row: the first example then returns 5, because the bottom-right 1 becomes a neighbor of the top row.

Pattern

Grid connected components. Builds on Number of Islands.

Keep going