Number of Distinct Islands

Given an R × C grid of 0s and 1s, an island is a maximal 4-directionally connected group of 1s. Two islands are the same if one can be translated (shifted, without rotation or reflection) to match the other. Return the number of distinct island shapes.

Hints

· Stuck? Reveal one nudge at a time.

Two islands are the same if one shifts onto the other — you need a position-independent fingerprint.

Anchor each island at its first cell and record relative offsets.

Alternatively, encode the DFS traversal as a move string with backtrack markers.

Common doubts

Subtracting a fixed reference removes absolute position, so translated islands produce identical offset sets.

Without it, two different shapes can produce the same sequence of moves; the 'B' records when the traversal returns, distinguishing them.

No — only translations. Handling rotations/reflections would require canonicalizing over all 8 transformations.

Interview follow-ups

· What an interviewer asks next.

Generate all 8 transformed signatures of each island and take the lexicographically smallest as the canonical key.

The relative-coordinate set is conceptually simplest; the DFS move string is compact and avoids sorting.

Fun facts

LeetCode 694 — the shape-aware sibling of number of islands.
The DFS path signature is a form of tree/graph canonical hashing.

Asked at

AmazonGoogleFacebook

Frequently Sometimes Occasionally

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 — the same shape.

Example 2

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 1
Four single-cell islands, all the same shape.

Constraints

- 1 <= R, C <= 500 - grid[i][j] is 0 or 1

Counting islands is easy; the twist is treating same-shape islands as one. The fix is to give each island a translation-invariant signature and count distinct signatures.

Two clean signatures:

Relative coordinates. Flood the island and record each cell's offset from a fixed anchor (the first cell). Shifting the island shifts every offset equally, so two translated islands produce the same offset set.
DFS path signature. Do a DFS in a fixed direction order and emit a character per move (D/U/R/L) plus a backtrack marker B. The traversal shape — not the absolute position — is captured, and the backtrack markers keep different shapes from colliding.

Either way, drop the signature into a set and return its size. O(R·C).

Prerequisites

Before you start

· Concepts used directly in the solution.

Flood fill. visit an island's cells.

Canonical signature. a position-independent fingerprint of a shape.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Are rotations/reflections the same shape?”

No — only translations count as the same.

“4- or 8-directional?”

4-directional.

The ideal opening — say it like this

I flood each island and build a translation-invariant signature — relative offsets from the first cell, or a DFS move-string.

I add each signature to a set and return its size.

Understand the problem

Worked example — two L-shaped islands in different corners

both flood to offsets {(0,0),(1,0),(1,1)} -> same signature -> counted once

Key observations

1Aha

Anchor removes position

Offsets from the first cell are identical for translated shapes.

2Aha

Backtrack markers matter

Without them, different DFS shapes can produce the same move string.

3Aha

Set of signatures = distinct shapes

The answer is the number of unique fingerprints.

Brute force vs optimal

	Relative coordinates	DFS path signature
Signature	offset set from the anchor	move string with backtracks
Time	O(R·C log)	O(R·C)
Idea	position-free coordinates	position-free traversal

Both group translated islands together and count the distinct groups. Full code is in the Approaches selector below.

Summary

Key takeaway

Give each island a translation-invariant signature — relative offsets from its anchor, or a DFS move string with backtrack markers — and count the distinct signatures. O(R·C).

for each island: sig = shape fingerprint; shapes.add(sig)
answer = len(shapes)