Number of Distinct Islands

Number of Distinct Islands

What is this problem about?

The Number of Distinct Islands problem gives you a binary grid where 1s represent land. Two islands are considered the same if one can be translated (shifted) to match the other — not rotated or reflected. Count the number of distinct island shapes. This coding problem uses DFS with path serialization to uniquely represent each island shape.

Why is this asked in interviews?

Microsoft, Meta, Amazon, TikTok, and Google ask this because it requires encoding the DFS traversal path of each island as a canonical string representation. Two islands have the same shape if and only if their DFS paths (relative to their starting cell) are identical. The union find, BFS, hash table, hash function, and DFS interview pattern is the core.

Algorithmic pattern used

DFS with relative path encoding. For each unvisited land cell, run DFS and record the traversal directions as a string (e.g., 'U','D','L','R' for moves, 'B' for backtrack). The path string represents the island's shape. Add each path to a set. The set size = number of distinct islands. Key: use relative coordinates (offset from the starting cell) or include backtrack markers.

Example explanation

Grid:

1 1 0 1 1
1 0 0 0 1
0 0 0 0 0
1 1 0 1 0
1 0 0 1 0

Island at (0,0): shape "DR" (down-right). Island at (0,3): same shape "DR" (shifted right). Same island → count as 1. Island at (3,0): different shape. Island at (3,3): different. Distinct islands = 3 (verify by comparing DFS paths).

Common mistakes candidates make

• Not including backtrack markers in the path — two different shapes can share the same path without backtrack info.
• Using absolute coordinates instead of relative offsets for the path.
• Forgetting to mark cells as visited during DFS.
• Not resetting the path string for each new island.

Interview preparation tip

Island shape encoding requires both the direction moves AND backtrack markers to uniquely identify shapes. Without backtracking markers, DFS paths can collide for different shapes. Practice encoding DFS paths for several manually drawn island shapes to verify your encoding is unambiguous. The relative coordinate approach (storing row_offset, col_offset pairs normalized to start at (0,0)) is an alternative — add all such pairs to a set as a frozenset for comparison.