Number of Distinct Islands
Asked at TikTok
Problem
Number of Distinct Islands asks how many different island shapes appear in a binary grid, where two islands are the same if one can be translated (not rotated or reflected) onto the other. It extends Number of Islands with a canonical-shape hashing step.
Asked At
| Company | Difficulty | |
|---|---|---|
| TikTok | Medium | View all TikTok questions → |
How to Think About It
Counting islands is standard DFS/BFS. The new part is deciding whether two islands have the same shape.
Option 1: record each cell of an island relative to the island's first cell ((r - r0, c - c0)). Because the DFS always starts at the top-left-most cell in scan order, identical shapes produce identical coordinate lists.
Option 2: record the DFS path as a string of directions, like "d r u b". Crucially, also append a backtrack marker when a call returns — without it, different shapes can produce the same sequence of moves.
Store each island's signature (as a tuple or string) in a hash set. The answer is the size of the set.
Walkthrough: two 2x2 squares anywhere in the grid both produce the relative coordinates [(0,0),(0,1),(1,0),(1,1)] -> one distinct shape.
Optimal Approach
Step 1: shapes = set().
Step 2: For each cell that is land and unvisited:
Run DFS from it, marking cells visited and appending (r - r0, c - c0) for every cell reached, where (r0, c0) is the start.
Add the tuple of offsets to shapes.
Step 3: Return len(shapes).
The DFS explores neighbors in a fixed order, so equal shapes give equal offset sequences.
Time: O(m * n). Space: O(m * n).
What Trips People Up in Real Interviews
Using absolute coordinates. The same shape at different positions must hash the same — normalize relative to a fixed starting cell.
Encoding only direction moves without backtrack markers. Two different shapes can then produce identical strings.
Considering rotations or reflections as equal. This problem only allows translation (Number of Distinct Islands II handles rotation).
Storing a list in a set in Python. Convert it to a tuple (or a string) first.
Solution Code
def numDistinctIslands(grid):
m, n = len(grid), len(grid[0])
shapes = set()
def dfs(r, c, r0, c0, shape):
if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != 1:
return
grid[r][c] = 2
shape.append((r - r0, c - c0))
dfs(r + 1, c, r0, c0, shape)
dfs(r - 1, c, r0, c0, shape)
dfs(r, c + 1, r0, c0, shape)
dfs(r, c - 1, r0, c0, shape)
for r in range(m):
for c in range(n):
if grid[r][c] == 1:
shape = []
dfs(r, c, r, c, shape)
shapes.add(tuple(shape))
return len(shapes)Frequently Asked Questions
What is the Number of Distinct Islands problem?
Number of Distinct Islands asks how many different island shapes appear in a binary grid, where two islands are the same if one can be translated (not rotated or reflected) onto the other. It extends Number of Islands with a canonical-shape hashing step.
How do you solve Number of Distinct Islands?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Number of Distinct Islands?
Number of Distinct Islands is asked at TikTok. It is a medium difficulty problem.
What are common mistakes on Number of Distinct Islands?
- Using absolute coordinates. The same shape at different positions must hash the same — normalize relative to a fixed starting cell.
- Encoding only direction moves without backtrack markers. Two different shapes can then produce identical strings.
- Considering rotations or reflections as equal. This problem only allows translation (Number of Distinct Islands II handles rotation).
- Storing a list in a set in Python. Convert it to a tuple (or a string) first.