Number of Islands

You'll treat the grid as a graph and run BFS from each new piece of land, counting one island per BFS. You need grid coordinates, sets, and a queue. Related chapter: graphs, BFS, and DFS.

1. The problem

You get a rectangular grid of "1" (land) and "0" (water). Count the islands: groups of land cells joined up, down, left, or right, but not diagonally. Everything outside the grid is water. Don't change the grid. This is LeetCode 200. Our function also handles an empty grid.

"Not diagonally" is the phrase that matters. In the second example, the two land cells touch only at a corner, so they're two islands.

2. A correct baseline

def baseline(grid):
    components=[]
    for r,row in enumerate(grid):
        for c,value in enumerate(row):
            if value!='1': continue
            neighbors={(r-1,c),(r+1,c),(r,c-1),(r,c+1)}
            combined={(r,c)}
            separate=[]
            for group in components:
                if group & neighbors:
                    combined |= group
                else:
                    separate.append(group)
            components=separate+[combined]
    return len(components)

assert baseline([list(r) for r in ['110','010','001']])==2
assert baseline([list(r) for r in ['10','01']])==2
assert baseline([list(r) for r in ['00','00']])==0

This keeps a set of cells for each island found so far. Each new land cell checks every island and merges the ones it touches. For V cells, that's O(V²) time in the worst case, with O(V) space. On a 300 × 300 grid, that's about eight billion steps.

The bottleneck. Each new cell searches every island so far, instead of exploring its own island directly.

3. The observation

Think of the grid as a graph. Each land cell is a node, joined to the land cells up, down, left, and right. An island is then a group of nodes you can reach from each other.

So scan the grid. When you find land you haven't seen, count one island, and run BFS from it to mark every cell of that island. Later cells of the same island are already marked, so they don't start a new count. Mark a cell as seen when you add it to the queue. Otherwise, two neighbors could both add the same cell.

4. The solution and a trace

from collections import deque

class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        """Rectangular string grid; four-neighbor land; preserve input."""
        if not grid or not grid[0]: return 0
        rows,cols=len(grid),len(grid[0])
        seen=set()
        islands=0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c]!='1' or (r,c) in seen: continue
                islands+=1
                seen.add((r,c)); queue=deque([(r,c)])
                while queue:
                    x,y=queue.popleft()
                    for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
                        nx,ny=x+dx,y+dy
                        if (0<=nx<rows and 0<=ny<cols and
                            grid[nx][ny]=='1' and (nx,ny) not in seen):
                            seen.add((nx,ny))
                            queue.append((nx,ny))
        return islands

solve=Solution().numIslands
assert solve([list(r) for r in ['110','010','001']])==2
assert solve([list(r) for r in ['10','01']])==2
assert solve([list(r) for r in ['00','00']])==0
assert solve([])==0

Trace the rows 110 / 010 / 001:

5. Why it works

Each BFS marks exactly one island. It moves only between neighboring land cells, so it stays on its island. And every reachable neighbor gets added to the queue, so it marks the whole island.

Each island is counted once. The scan reaches every land cell, so it finds every island. After the first BFS on an island, all its cells are marked, so no later cell starts a second count.

6. Cost, edge cases, and failure

Cost. Each cell is scanned once, and each land cell enters the queue once and checks four neighbors. That's O(rows × cols) time, growing in step with the grid. The seen set and the queue take O(rows × cols) space.

Edge cases. DFS with your own stack works just as well as BFS. Recursive DFS can hit Python's recursion limit on a big island. Using a separate seen set, instead of overwriting land with water, leaves the input unchanged.

Where it fails. Counting diagonal neighbors would merge islands that should be separate:

assert solve([list('10'),list('01')])==2
assert baseline([list('11')])==1  # Horizontal contact does connect.

import random,copy
rng=random.Random(200)
for _ in range(500):
    rows,cols=rng.randint(1,6),rng.randint(1,6)
    grid=[[rng.choice('01') for _ in range(cols)] for _ in range(rows)]
    before=copy.deepcopy(grid)
    assert solve(grid)==baseline(grid)
    assert grid==before
assert solve([['1']*300 for _ in range(300)])==1