Number of Distinct Islands — DFS Shape Hashing

Problem Statement#

LeetCode 694 — Number of Distinct Islands (Medium, Premium)

Given an m x n binary grid where 1 represents land and 0 represents water, return the number of distinct islands. Two islands are considered the same if one island can be translated (not rotated or reflected) to equal the other.

Constraints:

• 1 <= m, n <= 50
• grid[i][j] is 0 or 1

Example 1:

Input:
1 1 0 1 1
1 0 0 0 0
0 0 0 0 1
1 1 0 1 1
 
Output: 3
Explanation: The top-left island, top-right single cell island, and bottom island are all distinct shapes.

Example 2:

Input:
1 1 0 0 0
1 1 0 0 0
0 0 0 1 1
0 0 0 1 1
 
Output: 1
Explanation: Both islands have the same 2x2 square shape — translation makes them equal.

Example 3:

Input:
1 1 0 1 0
0 1 0 1 1
0 0 0 0 0
1 0 1 0 0
 
Output: 4
Explanation: Each island has a unique DFS traversal path encoding.

Why This Problem Matters#

This problem sits at the intersection of two core techniques: DFS graph traversal and hashing for deduplication. It appears in FAANG interviews as a litmus test for whether a candidate can:

1. Think beyond simple counting (Number of Islands) to shape identity
2. Design a canonical representation for an abstract object (a 2D island shape)
3. Apply hashing to a non-trivial domain (spatial paths)

The key challenge is figuring out how to encode an island's shape in a way that is position-independent (so the same shape at different locations hashes identically) but shape-specific (so different shapes always hash differently). This insight — relative path encoding — is the core transferable skill.

In practice, similar techniques appear when deduplicating tree structures, detecting duplicate subtrees, or comparing graph topologies. Any time you need a "canonical form" for a complex object, you're applying the same mental model.

The Core Insight#

The trick is to record not the absolute positions of an island's cells, but the sequence of DFS decisions made while exploring it. Every island is explored by starting at its topmost-leftmost cell and making four possible moves: Down (D), Up (U), Right (R), Left (L). When DFS backtracks (returns from a dead end), we record B for backtrack.

Because we always start DFS from the top-left cell of each island and always try directions in the same order, two islands that are translations of each other will produce identical path strings. Two islands with different shapes will produce different strings.

For example, an L-shaped island and a mirrored-L island will produce different path strings — this correctly identifies them as distinct, since rotations/reflections are not considered "same."

The path string is appended to a Python set, which stores only unique entries. The answer is len(shapes).

Visual Dry Run#

Grid:
1 1 0
1 0 0
0 0 1
 
Island 1: starts at (0,0)
  DFS visits (0,0) → path=['S']
  Go Down to (1,0) → path=['S','D']
  No more moves from (1,0) → backtrack → path=['S','D','B']
  Go Right to (0,1) from (0,0) → path=['S','D','B','R']
  No more moves from (0,1) → backtrack → path=['S','D','B','R','B']
  Final path tuple for island 1: ('S','D','B','R','B')
 
Island 2: starts at (2,2)
  DFS visits (2,2) → path=['S']
  No neighbors → just backtrack → path=['S','B']
  Final path tuple for island 2: ('S','B')
 
shapes = {('S','D','B','R','B'), ('S','B')}
Answer: 2 distinct islands

The critical observation: if there had been another L-shaped island at (5,5), its DFS would produce the same tuple ('S','D','B','R','B') and would not add a new entry to the set.

Common Mistakes#

1. Recording absolute positions instead of relative moves. If you add (r - start_r, c - start_c) tuples to the set, two islands at different locations with the same shape will produce the same relative coordinates — this does work, but you must normalize carefully to the same anchor point.

2. Forgetting backtrack markers. Without B, a cross-shaped island and an L-shaped island might produce the same sequence of direction characters. Backtrack markers distinguish "went right then down" from "went down then right."

3. Not resetting the path list between islands. Each island DFS should start with a fresh path list; reusing the old one corrupts the hash.

4. Starting DFS from any cell, not consistently the top-left. The encoding only works if all islands start from the same relative corner. Since we scan top-to-bottom, left-to-right, the first unvisited cell of each island is always its top-leftmost cell — this is automatic if you mark cells visited during DFS.

5. Using a list instead of a tuple when adding to the set. Lists are not hashable in Python; you must convert path to tuple(path) before adding to the set.

6. Modifying the grid without a visited set when the grid is read-only. Some variants require a separate visited array if you cannot mutate the input grid.

Solutions#

Python#

class Solution:
    def numDistinctIslands(self, grid: list[list[int]]) -> int:
        R, C = len(grid), len(grid[0])  # grid dimensions
        shapes = set()                   # store unique path encodings
 
        def dfs(r, c, path, direction):
            # base case: out of bounds or water or already visited
            if not (0 <= r < R and 0 <= c < C) or grid[r][c] != 1:
                return
            grid[r][c] = 0              # mark visited by clearing land
            path.append(direction)       # record the direction we came from
 
            # explore all 4 neighbors with their direction labels
            dfs(r + 1, c, path, 'D')   # down
            dfs(r - 1, c, path, 'U')   # up
            dfs(r, c + 1, path, 'R')   # right
            dfs(r, c - 1, path, 'L')   # left
 
            path.append('B')            # backtrack marker: returning from this cell
 
        for r in range(R):
            for c in range(C):
                if grid[r][c] == 1:     # found an unvisited island cell
                    path = []
                    dfs(r, c, path, 'S')   # 'S' = start anchor
                    shapes.add(tuple(path)) # tuple is hashable; add shape to set
 
        return len(shapes)              # number of unique shapes

JavaScript#

/**
 * @param {number[][]} grid
 * @return {number}
 */
var numDistinctIslands = function(grid) {
    const R = grid.length;          // number of rows
    const C = grid[0].length;       // number of columns
    const shapes = new Set();        // store unique path encodings as strings
 
    // DFS to encode island shape as direction path
    function dfs(r, c, path, dir) {
        // out of bounds or water or already visited
        if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] !== 1) return;
 
        grid[r][c] = 0;             // mark cell visited
        path.push(dir);             // record direction taken to reach this cell
 
        dfs(r + 1, c, path, 'D');  // try going down
        dfs(r - 1, c, path, 'U');  // try going up
        dfs(r, c + 1, path, 'R');  // try going right
        dfs(r, c - 1, path, 'L');  // try going left
 
        path.push('B');             // backtrack marker
    }
 
    for (let r = 0; r < R; r++) {
        for (let c = 0; c < C; c++) {
            if (grid[r][c] === 1) {         // start of a new island
                const path = [];
                dfs(r, c, path, 'S');        // 'S' = start
                shapes.add(path.join(','));   // join to get a string key
            }
        }
    }
 
    return shapes.size;             // unique island shapes
};

Complexity Analysis#

• Time: Every cell is visited at most once during DFS. Building path strings takes O(m*n) total across all islands.
• Space: The visited modification is in-place. The shapes set and recursion stack each consume at most O(m*n) in the worst case (one giant island).

Follow-up Questions#

1. Rotations and reflections: How would you handle islands that are the same when rotated 90/180/270 degrees or reflected? You'd need to compute all 8 canonical forms and pick the lexicographically smallest.

2. Larger grids: If the grid were 10,000 x 10,000, DFS recursion could overflow the stack. How would you convert to an iterative approach with an explicit stack?

3. Streaming updates: If cells are added one by one (like LC 305), how would you maintain the count of distinct shapes efficiently?

4. Count occurrences: Instead of just the count of distinct shapes, return each shape with how many times it occurs.

This Pattern Solves#

• Duplicate subtree detection (LC 652) — same canonical encoding idea applied to trees
• Isomorphic shape comparison in any domain
• DFS path encoding for uniqueness — anywhere you need a fingerprint for a traversal

Key Takeaways#

• Use relative path encoding: record the sequence of DFS directions + backtrack markers, not absolute coordinates
• Relative encoding makes shape signatures translation-invariant — the same shape starting at different positions produces identical strings
• Include backtrack markers (e.g., "0") at the end of each DFS direction to distinguish different branching structures
• Add all shape signatures to a set — the set size at the end equals the number of distinct islands
• Time O(mn), space O(mn) — each cell visited once; the set stores at most m*n characters of shape strings
• This relative-path canonical form applies to any "count structurally unique connected components" problem
• Without backtrack markers, DFS paths from different tree structures can hash to the same string — always include them