Distinct Island Shapes
MediumGraphs
Problem
A cartographer wants to know how many different island shapes appear on a map. The map grid uses 1 for land and 0 for water; islands are groups of land connected horizontally or vertically.
Two islands have the same shape when one can be slid (translated) onto the other exactly. Rotations and reflections do not count as the same shape. Return the number of distinct shapes.
Example 1
- Input:
- grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
- Output:
- 1
Both islands are 2 × 2 squares.
Example 2
- Input:
- grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
- Output:
- 3
The two horizontal dominoes match. The two L-shaped islands are mirror images of each other, so they count separately.
Constraints
- 1 ≤ rows, cols ≤ 50
- grid[r][c] is 0 or 1
Hint
Show the first hint
You need a way to describe an island so that two translated copies get the same description.
Walkthrough
How to approach it
01Clarify before coding
- Are rotated or mirrored islands the same shape? No, only translation.
- Is connectivity 4-directional? Yes.
- Do sizes matter? Yes, shapes of different sizes are always different.
02Brute force
Extract every island as a list of cells, then compare each pair by trying to align one onto the other.
Cost: O(k² · s) for k islands of size s, plus alignment work; on a 50 × 50 map with hundreds of islands it is slow and fiddly.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.