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 what differs.
Fun fact: Number of Distinct Islands can hash an island by the directions its DFS takes, but 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 (
oRRDBRBBBBagainstoRRDRBBBBB). It is one line, and without it the solution can pass a few small samples and still merge different shapes.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: the flood fill is the easy part. Decide what to record while it runs (a border flag, two corners, or a path signature) and each of these problems becomes the same short traversal 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. This is the lesson's Approach 2. Approach 1 floods each island and keeps a "touched the edge" flag, which works but must keep exploring after reaching the border rather than returning early, or the component is left half-marked and gets counted again. Approach 3 is union-find with a virtual "outside" node that every border land cell joins; it leaves the grid untouched, at O(mn alpha(mn)) time. All three are linear in practice, and the stack for the flood is O(mn) in the worst case, so use an explicit stack on a 100 x 100 grid.
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 share an edge, 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) time and O(1) extra space beyond the output. This only works because the problem guarantees rectangles, and saying that out loud is the point. The guarantee is what buys the simpler algorithm; without it you would be back to a flood fill tracking min and max row and column (the lesson's Approach 1, which costs O(mn) space for the stack or queue and visited marks). The lesson's Approach 3 finds any unseen cell, walks to the far corner and zeroes the rectangle; it mutates the input, so I prefer the corner test.
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. The lesson's Approach 1 is the alternative: record each cell's offset from the island's first cell, (r - r0, c - c0), as a frozen set. It needs no marker because it stores the geometry directly rather than a walk. Both are O(mn) time and O(mn) space, and the DFS version's recursion goes as deep as the island is long (2,500 cells on a 50 x 50 grid), so raise Python's recursion limit or use the BFS offsets version.
4. A 30-second worked example (closed islands)
grid = [[0,0,1,0,0], [0,1,0,1,0], [0,1,1,1,0]], where 0 is land and 1 is water.
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
- Hole filling in binary images. The holes are background regions that cannot reach the image border. SciPy's
binary_fill_holesfills exactly those, and counting them is Number of Closed Islands. - Bounding boxes of blobs. Labelling connected regions of a mask and reporting each box is a routine image-processing step. Farmland is the special case where the region is its own box.
- Canonical forms. Reducing an object to a representation that is equal exactly when the objects are equivalent, then hashing it, is the same move as sorting letters to group anagrams.
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. The lesson also covers the edge-flag flood and union-find with an outside node.
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. The lesson compares this with flood fill and mark-as-you-go.
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, or by its cell offsets from the first cell.
Pattern: canonical shape as a hash key. Target: O(mn) time and space.
7. Common pitfalls
- Omitting the backtrack marker in the shape signature, which silently merges genuinely different islands (
11over1.and1.over11both giveoDR). - Reading the closed-islands encoding backwards.
0is land and1is 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. A solid 100 x 100 grid is 10,000 frames deep, past Python's default limit of 1000, so use an explicit stack or an iterative BFS.
8. Key takeaways
- One traversal, three accumulators. The flood fill is never the interesting part.
- A canonical form is a hash key: that is the whole trick behind counting distinct shapes.
- The backtrack marker is not optional; there is a two-row counterexample without it. Storing offsets from the first cell avoids the problem.
- Guarantees in the statement buy simpler algorithms. Rectangles that never share an edge mean no traversal at all.
- Border elimination first is cleaner than threading a flag through a recursion.
- Check the land/water encoding before writing a line: it is inverted here (
0is land). - 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.
Number of Closed Islands
Core idea: An island is closed when no path of land cells leads from it to the edge of the grid. So remove the open ones first: flood every land cell on the border, sinking each component connected to the outside, then count the land components that survive. Two passes, and no "touched the edge" flag threaded through the recursion. Watch the encoding: here
0is land and1is water, the reverse of the usual island problem. Connectivity is 4-directional, so a diagonal touch does not leak. O(mn) time.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson