Number of Distinct Islands
Count how many differently shaped islands a grid contains, where two islands are the same if one can be shifted onto the other, by hashing each island's cell offsets.
Problem Understanding
Number of Distinct Islands (LeetCode 694): in a grid of 0 (water) and 1 (land), an island is a group of land cells connected up, down, left or right. Two islands are the same if one can be translated (not rotated or reflected) onto the other. Return the number of distinct islands.
Examples: [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]] → 1; [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]] → 3.
The Intuition: Describe Each Island Relative to Itself
Absolute positions differ between copies, but positions relative to a fixed corner of the island do not:
- Find islands with the same scan and DFS as Number of Islands.
- Record the shape as each cell's offset from the cell where the DFS began.
- Count distinct shapes by putting each offset list into a set.
The same "label each island, then reason about the labels" step drives Making A Large Island.
Interactive Walkthrough
COLOUR AND LETTER = SHAPE · 1 = LAND NOT YET VISITED · · = WATER
SCAN FOR LAND
cells
:
shapes
0
Scan row by row for land not yet visited
Next
DFS from (0, 0): 3 cells, offsets (0,0) (1,0) (0,1)
grid
Each shape gets its own colour and letter, so a repeated shape shows up in a colour already on the grid. Try Rotated L: the two L shapes look alike but are rotations, so they count twice.
Dry Run Table
Input: [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]].
| DFS start | Offsets (DFS order) | Shape |
|---|---|---|
| (0, 0) | (0,0) (1,0) (0,1) | new: A |
| (0, 3) | (0,0) (0,1) | new: B |
| (2, 4) | (0,0) (1,0) (1,-1) | new: C |
| (3, 0) | (0,0) (0,1) | same as B |
Answer: 3.
The Solution Template
Scan, DFS with offsets, and a set of shapes.
Number of Distinct Islands Code
1var numDistinctIslands = function(grid) {2 const rows = grid.length, cols = grid[0].length;3 const shapes = new Set();4 const dfs = (r, c, r0, c0, shape) => {5 if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] !== 1) return;6 grid[r][c] = 0;7 shape.push(`${r - r0},${c - c0}`);8 dfs(r + 1, c, r0, c0, shape);9 dfs(r - 1, c, r0, c0, shape);10 dfs(r, c + 1, r0, c0, shape);11 dfs(r, c - 1, r0, c0, shape);12 };13 for (let r = 0; r < rows; r++) {14 for (let c = 0; c < cols; c++) {15 if (grid[r][c] === 1) {16 const shape = [];17 dfs(r, c, r, c, shape);18 shapes.add(shape.join(';'));19 }20 }21 }22 return shapes.size;23};
Edge Cases & Common Mistakes
- Absolute coordinates: translated copies never match; always subtract the start cell.
- Separators in the string key: "1,12" and "11,2" collide without a delimiter between offsets.
- Changing the direction order between islands: the same shape could produce two different lists.
- All water: 0 islands, 0 shapes.
- Rotations: they are different shapes here; only LeetCode 711 treats them as equal.
Summary
Scan the grid; DFS each new island in a fixed order, recording each cell's offset from the start, and add the list to a set. The set's size is the answer. O(m · n) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet