MediumHash TableDepth-First SearchBreadth-First SearchUnion FindHash FunctionUpdated Sep 2026

694. Number of Distinct Islands

Asked at TikTok

Difficulty

Medium

Time

O(m * n)

Space

O(m * n)

Pattern

Hash Table

Companies

1

Problem

You are given a 2D grid of 0s and 1s. A 1 is land and a 0 is water. An island is a group of land cells connected 4-directionally (up, down, left, right — not diagonally).

Two islands count as the same shape if you can slide one of them (translate it) so it lands exactly on top of the other. You may not rotate or flip an island to make it match. So a shape and its mirror image are different shapes.

Return the number of distinct island shapes in the grid. Count each shape once, no matter how many times it appears.

Two islands, one shape

grid11000110000001100011The green island and the orange island have the same2x2 shape, so the answer is 1.
Both islands are 2x2 squares, so after sliding one onto the other they match and count as a single shape.

Constraints

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

Examples

Example 1
Inputgrid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
Output1
WhyThere are two islands, but both are 2x2 squares. Sliding one square onto the other makes them match, so they are the same shape. The answer is 1.
Example 2
Inputgrid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
Output3
WhyThe top-left island is an L shape, the top-right island is a single cell, and the bottom-left island is a different L shape (a mirror of the first one). The bottom-right cell joins the top-right island. Since mirror images do not match, the L shapes count separately, giving 3 distinct shapes.

Asked At

1 companies
CompanyDifficulty
TikTokMediumView all TikTok questions →

How to Think About It

1

Counting islands is standard DFS/BFS. The new part is deciding whether two islands have the same shape.

2

Option 1: record each cell of an island relative to the island's first cell ((r - r0, c - c0)). Because the DFS always starts at the top-left-most cell in scan order, identical shapes produce identical coordinate lists.

3

Option 2: record the DFS path as a string of directions, like "d r u b". Crucially, also append a backtrack marker when a call returns — without it, different shapes can produce the same sequence of moves.

4

Store each island's signature (as a tuple or string) in a hash set. The answer is the size of the set.

5

Walkthrough: two 2x2 squares anywhere in the grid both produce the relative coordinates [(0,0),(0,1),(1,0),(1,1)] -> one distinct shape.

Optimal Approach

Step 1: shapes = set().
Step 2: For each cell that is land and unvisited:
Run DFS from it, marking cells visited and appending (r - r0, c - c0) for every cell reached, where (r0, c0) is the start.
Add the tuple of offsets to shapes.
Step 3: Return len(shapes).

The DFS explores neighbors in a fixed order, so equal shapes give equal offset sequences.

Time: O(m * n). Space: O(m * n).

Give each island a relative-coordinate signature

grid11000110000001100011Start at the top-left land cell (0,0) and run DFS overthe whole island.offsets from (0,0):(0,0) (0,1) (1,0) (1,1)offsets from (2,3):(0,0) (0,1) (1,0) (1,1)same signature -> one shapeshapes = set()answer = len(shapes)
For every island we record each cell as an offset from the island's first cell, then put that list in a set.
ComplexityTime O(m * n)Space O(m * n)Each cell is visited once by the DFS, and the worst case stores one offset per land cell in the shape set.

What Trips People Up in Real Interviews

1

Using absolute coordinates. The same shape at different positions must hash the same — normalize relative to a fixed starting cell.

2

Encoding only direction moves without backtrack markers. Two different shapes can then produce identical strings.

3

Considering rotations or reflections as equal. This problem only allows translation (Number of Distinct Islands II handles rotation).

4

Storing a list in a set in Python. Convert it to a tuple (or a string) first.

Solution Code

O(m * n) time
def numDistinctIslands(grid):
    m, n = len(grid), len(grid[0])
    shapes = set()

    def dfs(r, c, r0, c0, shape):
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != 1:
            return
        grid[r][c] = 2
        shape.append((r - r0, c - c0))
        dfs(r + 1, c, r0, c0, shape)
        dfs(r - 1, c, r0, c0, shape)
        dfs(r, c + 1, r0, c0, shape)
        dfs(r, c - 1, r0, c0, shape)

    for r in range(m):
        for c in range(n):
            if grid[r][c] == 1:
                shape = []
                dfs(r, c, r, c, shape)
                shapes.add(tuple(shape))
    return len(shapes)

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Number of Distinct Islands problem?

Number of Distinct Islands asks how many different island shapes appear in a binary grid, where two islands are the same if one can be translated (not rotated or reflected) onto the other. It extends Number of Islands with a canonical-shape hashing step.

How do you solve Number of Distinct Islands?

The optimal approach runs in O(m * n) time and O(m * n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Number of Distinct Islands?

Number of Distinct Islands is asked at TikTok. It is a medium difficulty problem.

What are common mistakes on Number of Distinct Islands?
  • Using absolute coordinates. The same shape at different positions must hash the same — normalize relative to a fixed starting cell.
  • Encoding only direction moves without backtrack markers. Two different shapes can then produce identical strings.
  • Considering rotations or reflections as equal. This problem only allows translation (Number of Distinct Islands II handles rotation).
  • Storing a list in a set in Python. Convert it to a tuple (or a string) first.