Skip to main content

694 - Number of Distinct Islands

Difficulty: Medium | Pattern: DFS + Shape Hashing | Company tags: Google, Amazon, Facebook

Problem Statement​

You are given an m x n binary grid where 1 represents land and 0 represents water. An island is a group of 1s connected 4-directionally.

Two islands are considered the same if and only if one island can be translated (not rotated or reflected) to equal the other.

Return the number of distinct islands.

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 2x2 squares have the same shape)

Example 2:

Input: grid =
[[1,1,0,1,1],
 [1,0,0,0,0],
 [0,0,0,0,1],
 [1,1,0,1,1]]
Output: 3

Approach: DFS with Path Signature — O(mn), O(mn)​

Key insight: Record the DFS traversal path relative to the island's starting cell. Two islands have the same path string → same shape. Store paths in a set.

def numDistinctIslands(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    shapes = set()
    
    def dfs(r, c, direction, path):
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != 1:
            return
        grid[r][c] = 0  # mark visited
        path.append(direction)
        dfs(r+1, c, 'D', path)
        dfs(r-1, c, 'U', path)
        dfs(r, c+1, 'R', path)
        dfs(r, c-1, 'L', path)
        path.append('B')  # backtrack marker (important!)
    
    for r in range(m):
        for c in range(n):
            if grid[r][c] == 1:
                path = []
                dfs(r, c, 'S', path)
                shapes.add(tuple(path))
    
    return len(shapes)

Why Backtrack Markers Matter​

Without backtrack markers, the paths SDB and SBD could encode the same string and cause false shape equality. The 'B' token disambiguates when we returned from a branch vs continued forward.

Dry Run​

2x2 island at top-left, starting at (0,0):

  • dfs(0,0,'S') → path=['S'], go Down
  • dfs(1,0,'D') → path=['S','D'], go Down (out) Up (visited) Right
  • dfs(1,1,'R') → path=['S','D','R'], go Down (out) Up→(0,1) Right (out) Left (visited)
  • dfs(0,1,'U') at (1,1) up = path+=['U','B','B','B']
  • Overall: tuple('S','D','R','U','B','B','B','B')

Same for the 2x2 island at bottom-right → same tuple → set size = 1 ✓

Complexity​

  • Time: O(m x n)
  • Space: O(m x n)