Number of Distinct Islands - Solution & Explanation

Problem Overview: You receive a binary grid where 1 represents land and 0 represents water. Islands are groups of horizontally or vertically connected land cells. The task is to count how many distinct shapes of islands exist in the grid. Two islands are considered the same if their shapes match after translation (shifting position), regardless of where they appear in the grid.

Approach 1: Brute Force Shape Comparison (O((m*n)^2) time, O(m*n) space)

Traverse the grid and collect all cells belonging to each island using a traversal such as Depth-First Search or Breadth-First Search. Store the absolute coordinates of each island's cells. After discovering every island, compare each island's coordinate set against all previously found islands to determine if the shape matches after translation. Normalizing coordinates requires shifting them relative to a base cell before comparison. This works but becomes expensive because every new island may need comparison with many existing shapes.

Approach 2: Relative Coordinate Hashing (O(m*n) time, O(m*n) space)

Instead of storing absolute positions, record each island's cells relative to the first discovered land cell of that island. During a DFS traversal, compute offsets like (row - baseRow, col - baseCol). This converts every island into a normalized shape representation independent of location. Store the sequence of relative coordinates in a set using a Hash Table. If another island produces the same normalized coordinate list, it represents the same shape and will not increase the count. Each cell is visited once, so the traversal runs in linear time.

Approach 3: DFS Path Signature Encoding (O(m*n) time, O(m*n) space)

Another common technique records the traversal path itself. While performing DFS, append characters representing movement directions (for example U, D, L, R) and a marker when backtracking. The resulting traversal string uniquely describes the island's structure. Two islands with identical shapes generate the same traversal signature. Store these signatures in a hash set to count distinct patterns. This avoids storing full coordinate lists and works well with recursive DFS.

Recommended for interviews: DFS with relative coordinate hashing or path signature encoding. Both achieve O(m*n) time by visiting each cell once and storing normalized island shapes in a set. Interviewers expect you to recognize that island position is irrelevant and that the shape must be normalized before hashing. Starting with a brute-force comparison shows understanding, but moving to a hashing-based solution demonstrates strong problem-solving and familiarity with graph traversal.