Number of Distinct Islands II

Number of Distinct Islands II

What is this problem about?

The Number of Distinct Islands II extends the first problem to consider all 8 transformations (rotations by 90°, 180°, 270°, and their reflections) as the same island. Two islands are considered identical if one can be obtained from the other through any rotation or reflection. This hard coding problem requires normalizing island shapes across all 8 symmetry transformations.

Why is this asked in interviews?

Meta, Amazon, and Google ask this because it requires implementing all 8 symmetry transformations on a set of relative coordinates and then canonicalizing to a minimum representative. The array, matrix, union find, BFS, hash table, sorting, hash function, and DFS interview pattern is all exercised here.

Algorithmic pattern used

DFS + 8 transformations + canonical normalization. After DFS, collect the set of relative coordinates (dr, dc) for each island. Apply all 8 transformations: (r,c), (-r,c), (r,-c), (-r,-c), (c,r), (-c,r), (c,-r), (-c,-r). For each transformed set, normalize by shifting so the minimum row and column are 0. Sort each transformed set. Take the lexicographically smallest sorted set as the canonical representation. Add to a set of canonical shapes.

Example explanation

Island with cells at offsets: [(0,0),(0,1),(1,0)] (L-shape). After rotation 90°: [(0,0),(1,0),(0,-1)] → normalized: [(0,0),(0,1),(1,0)] (same L-shape in different orientation). All 8 transformations yield either the L-shape or its mirror. Both are counted as the same distinct island. Canonical representation = sorted minimum.

Common mistakes candidates make

• Only applying rotations but forgetting reflections (8 total, not 4).
• Incorrect normalization (forgetting to shift to minimum row and column).
• Using floating-point rotation formulas instead of discrete (r,c) transformations.
• Sorting individual coordinates instead of the full set.

Interview preparation tip

Symmetry normalization is a pattern that appears in shape uniqueness problems, crystal structure analysis, and puzzle solving. The 8 transformations of a 2D shape are: all combinations of (±r, ±c) and (±c, ±r). After applying each, normalize to the minimum bounding corner. Sort the resulting coordinate list. The smallest lexicographic version is the canonical form. Practice this on simpler cases (only 4 rotations) before tackling all 8 transformations.