DSA problem
Number of Distinct Islands
You are given an m x n binary matrix grid. An island is a group of 1s (representing land) connected 4-directionally (horizontal or vertical). You may assume all four edges of the grid are surrounded by water. Two islands are considered the same if and only if one island can be translated (without rotating or reflecting) to equal the other. Return the number of distinct islands.
The challenge here is not finding the islands — that is a standard DFS flood-fill — but defining a canonical fingerprint for each island so that translated copies of the same shape are recognized as identical. Two islands that look identical after sliding (but without rotating or mirroring) must produce the same fingerprint, while truly different shapes must produce different fingerprints.
The cleanest fingerprint is the sequence of cell offsets relative to the island's starting cell. When you DFS into an island starting at cell (r0, c0), record each visited cell as the pair (r - r0, c - c0). Because the DFS traversal order is deterministic for a fixed neighbour order, two islands that are translations of each other generate the exact same ordered sequence of relative coordinates.
Insert each island's fingerprint into a set and return the set's size. The total work is one flood-fill over the grid plus constant-time set operations per cell, giving O(m * n) time and O(m * n) space in the worst case where the grid is one giant island.
Examples
grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]1grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]3grid = [[1,1,0],[0,1,1],[0,0,0],[1,1,1],[0,1,0]]2Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 50
- grid[i][j] is either 0 or 1.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.