Connected Components

What is this?

Counting components is a 101 skill. All three problems here run the same flood fill and then ask something the count alone cannot answer: is this component enclosed, what rectangle does it occupy, and is its shape one I have already seen. The traversal is identical every time; what you record during it is the whole problem.

💡 Fun fact: Number of Distinct Islands hashes an island by recording the directions its DFS takes — and the recording is wrong without a marker on the way out of each cell. These two shapes both produce oRRDR with directions alone:

####            ###.
..#.            ..##

Appending a single backtrack character when a call returns separates them, and separates every other colliding pair. It is one line, and without it the solution passes the samples and fails the judge.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: the flood fill is free. Decide what to record while it runs — a border flag, two corners, or a path signature — and each of these problems becomes the same twelve lines with a different accumulator.

1. Record whether it touched the border

An island is closed if the flood fill never reaches the edge of the grid. The cleanest form removes the open ones first:

for r in range(m):                                  # sink everything border-connected
    for c in range(n):
        if (r in (0, m-1) or c in (0, n-1)) and grid[r][c] == 0:
            flood(r, c)

closed = 0
for r in range(m):
    for c in range(n):
        if grid[r][c] == 0:
            flood(r, c); closed += 1                # whatever survives is enclosed

Two passes, no flags to thread through the recursion. The alternative — returning a boolean up from the DFS — works but must keep exploring after reaching the border rather than returning early, or the component is left half-marked and gets counted again.

Watch the encoding: here 0 is land and 1 is water, the reverse of the usual island problem, which catches people who typed the shape from memory.

2. Record the corners

Groups are rectangles and never touch, which means no traversal is needed at all. A cell is a top-left corner exactly when nothing is above it and nothing is to its left; from there the extent is two straight walks:

for r in range(m):
    for c in range(n):
        if land[r][c] == 1 and (r == 0 or land[r-1][c] == 0) \
                           and (c == 0 or land[r][c-1] == 0):
            r2, c2 = r, c
            while r2 + 1 < m and land[r2+1][c] == 1: r2 += 1
            while c2 + 1 < n and land[r][c2+1] == 1: c2 += 1
            out.append([r, c, r2, c2])

No visited set, no recursion, O(mn) total. This only works because the problem guarantees rectangles, and saying that out loud is the point — the guarantee is what buys the simpler algorithm, and without it you would be back to a flood fill tracking min and max row and column.

3. Record the path

def dfs(r, c, d):
    if not in_bounds(r, c) or grid[r][c] == 0 or (r, c) in seen: return
    seen.add((r, c)); sig.append(d)
    dfs(r+1, c, 'D'); dfs(r-1, c, 'U'); dfs(r, c+1, 'R'); dfs(r, c-1, 'L')
    sig.append('b')                                  # ← the backtrack marker

Starting each island from its first cell in row-major order makes the walk deterministic, so identical shapes produce identical strings and translation is handled for free. The 'b' is what makes the encoding injective. An equally good alternative records each cell's offset from the island's first cell — (r − r0, c − c0) — as a frozen set, which needs no marker because it stores the geometry directly rather than a walk.

4. A 30-second worked example (closed islands)

grid = [[0,0,1,0,0], [0,1,0,1,0], [0,1,1,1,0]] — 0 is land, 1 is water.

pass 1: sink every 0 reachable from the border
        column 0 is all land and column 4 is all land → both sink entirely,
        taking (0,0),(0,1) and (0,3),(0,4) with them

pass 2: the only 0 left is (1,2), boxed in by
        (0,2)=1 above, (2,2)=1 below, (1,1)=1 left, (1,3)=1 right

closed = 1

The single enclosed cell is the answer, and it is enclosed only because all four of its neighbours are water. Any leak — including a diagonal one, which does not count as a connection — would have sunk it in the first pass.

5. Where you'll actually meet this

• Image segmentation. Connected-component labelling is the classic operation; "does this region touch the frame edge" decides whether an object was fully captured.
• Land and parcel systems. Bounding rectangles for contiguous plots is the farmland problem exactly.
• Sprite and asset tooling. Deduplicating identical sprites across a sheet is shape hashing.
• Medical imaging. Counting lesions of a given shape, and discarding regions clipped by the scan boundary.
• Procedural map generation. Verifying that a generated cave is enclosed, and rejecting duplicate room shapes.

6. Problems in this chapter

▶ Number of Closed Islands

Count islands not touching the border. Sink every border-connected component first, then count what survives.
Pattern: flood fill + border elimination. Target: O(mn) time, O(mn) worst-case stack.

▶ Find All Groups of Farmland

Return the corners of each rectangular group. Detect top-left corners by their empty neighbours and walk right and down.
Pattern: corner detection, no traversal. Target: O(mn) time, O(1) extra space.

▶ Number of Distinct Islands

Count islands distinct up to translation. Hash each island by its DFS path, with a marker recorded on the way out.
Pattern: canonical shape as a hash key. Target: O(mn) time.

7. Common pitfalls 🚫

• Omitting the backtrack marker in the shape signature, which silently merges genuinely different islands.
• Reading the closed-islands encoding backwards. 0 is land and 1 is water here.
• Returning early from the DFS on reaching the border, which leaves a component partly unvisited and counted twice.
• Treating diagonals as connections. All three problems are four-directional.
• Flood-filling the farmland problem when corner detection is both simpler and faster — and not saying why the rectangle guarantee allows it.
• Not normalising the shape's starting point, which makes translated copies hash differently.
• Recursing on a large grid without considering the stack; an explicit stack or an iterative BFS is safer at scale.

8. Key takeaways

1. One traversal, three accumulators. The flood fill is never the interesting part.
2. A canonical form is a hash key — that is the whole trick behind counting distinct shapes.
3. The backtrack marker is not optional; there is a two-row counterexample without it.
4. Guarantees in the statement buy simpler algorithms. Rectangles mean no traversal at all.
5. Border elimination first is cleaner than threading a flag through a recursion.
6. Check the land/water encoding before writing a line — it is inverted here.
7. Why interviewers like it: everyone can flood fill, so the question is entirely what you choose to record while doing it.

Order: Number of Closed Islands → Find All Groups of Farmland → Number of Distinct Islands.