Introduction to Island Pattern

Every cell is visited at most once, so the time is O(R * C) for R rows and C columns. The space is the same in the worst case. A single island can fill the grid, and the traversal has to hold it.

Marking is what makes this correct. Most solutions overwrite the land cell with water instead of keeping a separate visited grid, which saves memory. Ask the interviewer whether the input may be modified before doing that.

Recognize it when

Use the Island pattern when the question shows these signs.

• The input is a two dimensional grid of cells.
• Cells are joined to their neighbours by position rather than by a given list of edges.
• The question asks about regions, areas, groups, or shapes inside the grid.
• The wording includes island, region, flood, or surrounded.
• You need to know how many separate connected areas the grid contains.

It is not this pattern when:

• The connections come as a list of pairs. That is a normal graph.
• The grid is a maze and you need the shortest route. Use Breadth First Search and count the rounds, which is the graph pattern rather than this one.
• Each cell's answer is built from cells already computed, with no exploration. That is Dynamic Programming.

The template

function countIslands(grid):
    count = 0

    for row from 0 to rows - 1:
        for col from 0 to cols - 1:
            if grid[row][col] is land:
                count = count + 1
                sink(grid, row, col)           # claim this whole island

    return count


function sink(grid, row, col):
    if row or col is outside the grid:  return
    if grid[row][col] is not land:      return

    grid[row][col] = water                     # mark before recursing

    sink(grid, row + 1, col)
    sink(grid, row - 1, col)
    sink(grid, row, col + 1)
    sink(grid, row, col - 1)

Two guards do the real work. The bounds check keeps you inside the grid, and the land check stops you revisiting. Both must come before anything else, and the marking must happen before the four calls or the recursion will loop.

Variants in this chapter

The border trick in row four is worth learning on its own. When a question asks for regions that do not touch the edge, it is almost always easier to remove the ones that do.

Watch out for

• Checking bounds after reading the cell. Reading grid[row][col] before testing the coordinates raises an error at the edges. The order of the two guards is not a matter of taste.
• Marking after the recursive calls. Mark the cell before you explore its neighbours, or two cells will keep calling each other.
• Counting diagonals as neighbours. Most questions mean four directions. Some mean eight. Read the question and say which one you assumed.
• Overwriting the input without asking. Sinking islands destroys the grid. That is usually fine, and it is still worth saying out loud.
• Deep recursion on a large grid. A grid that is all land recurses once per cell, which can overflow the stack. A queue avoids that.

How this compares with nearby patterns

This pattern is not really separate from Graphs. It is the same traversal with the adjacency list replaced by four coordinate offsets. If you can write one, you can write the other.

Key Takeaways

• A grid is a graph where each cell's neighbours are the four cells beside it.
• The outer loop finds new islands and the inner traversal claims them.
• Guard the bounds first, then the cell value, then mark before recursing.
• Time and space are both O(R * C) in the worst case.
• Removing the regions that touch the border is the usual route to "closed" or "surrounded" questions.

Let's apply it to the first problem, Number of Islands.