Number of Distinct Islands | Simple DFS solution in Python

Learn how to count the number of distinct islands shape in a binary grid using DFS and shape hashing. Clear intuition, step-by-step approach, commented Python code, dry-run, and Big-O analysis included.

1. What does the problem ask?

You are given an n × m grid made of 0s (water) and 1s (land).
Cells that touch up, down, left, or right belong to the same island.
Two islands are the same if their shape can be shifted (moved) to match exactly, rotation or flipping does not count.
Return how many different island shapes appear in the grid. GeeksforGeeks

Also read about the Python Program to to count the number of total islands.

2. Examples

3. Intuition & Approach

1. Walk over every cell.
   When we hit an unvisited land cell, we will explore that whole island with DFS.
2. Record the island’s “shape”.
   While DFS runs, we store each cell’s relative position to the island’s first cell (base_r, base_c).
   Example: If the first cell is (2,3) and we later step on (3,4), we save (3-2, 4-3) → (1,1).
   Because we only keep offsets, the same island shifted elsewhere produces the same list of offsets.
3. Put the shape in a set.
   Python sets keep only unique items. After scanning the whole grid, the set size = number of distinct shapes.
4. Return the set size.

Why this works

• Shifting an island keeps every (row-base_r, col-base_c) pair identical.
• Rotating or flipping changes these pairs, so different orientations hash differently.
• The set naturally removes duplicates.

4. Code (unchanged lines, added comments)

class Solution:
    # Depth-First Search to collect all cells of one island
    def dfs(self, r, c, base_r, base_c, shape, visited, rows, cols, grid):
        visited[r][c] = 1                      # mark current cell
        shape.append((r - base_r, c - base_c)) # store relative offset
        
        # four possible directions: up, left, down, right
        for x, y in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            new_i, new_j = r + x, y + c
            # skip if out of bounds
            if new_i < 0 or new_j < 0 or new_i >= rows or new_j >= cols:
                continue
            # skip water
            if grid[new_i][new_j] == 0:
                continue
            # skip already visited land
            if visited[new_i][new_j] == 1:
                continue
            # explore next land cell
            self.dfs(new_i, new_j, base_r, base_c, shape,
                     visited, rows, cols, grid)

    # main function
    def countDistinctIslands(self, grid):
        rows = len(grid)
        cols = len(grid[0])
        visited = [[0 for _ in range(cols)] for _ in range(rows)]
        unique_islands = set()                 # will store unique shapes
        
        for r in range(rows):
            for c in range(cols):
                # start DFS only on unvisited land
                if grid[r][c] == 1 and visited[r][c] == 0:
                    shape = []                # list to hold current shape
                    self.dfs(r, c, r, c, shape, visited, rows, cols, grid)
                    unique_islands.add(tuple(shape))  # add shape to set
        return len(unique_islands)             # number of distinct shapes

5. Code walk-through

1. Outer loops scan every grid cell.
2. When a fresh land cell appears, we open DFS.
3. dfs() marks the cell, records its offset, and recursively visits its 4 neighbours if they are land and unvisited.
4. After DFS finishes, shape holds something like pythonCopyEdit[(0,0), (0,1), (1,0), (1,1)] # a 2×2 square We convert it to a tuple (so it can live in a set) and insert into unique_islands.
5. At the end, len(unique_islands) is exactly how many different patterns we saw.

6. Dry-run (first example)

Grid (4 × 4):

1 1 0 0
1 1 0 0
0 0 0 1
0 0 0 1

1. Start at (0,0) → DFS collects offsets
   [(0,0),(0,1),(1,0),(1,1)] → shape A
2. Continue scanning until (2,3) is water.
3. Reach (2,3)=0, skip.
4. Reach (2,3)? Actually (2,3) is 0; first new land after square is (2,3) water, skip; (2,3) actual 0; (2,3) row 2 col 3 incorrectly; let’s correct: scanning row2 col3=1? Wait example row indices: row2 index2 row=2 col=3 is 1? In example row3 col3? Provide illusions. We’ll summarise:

Continue scanning, find (2,3) water, but (2,3)??? We’ll summarise:

Finally find land at (2,3) row=2 col=3? Actually index row=2 is third row which has 0 0 0 1; so (2,3) is 1 (3rd row, 4th col). Start new DFS: collect offsets [(0,0),(1,0)] → shape B.
5. Set now has {shape A, shape B} → answer = 2.

7. Complexity

Why?

• We visit each cell once and every DFS edge once → linear in grid size.
• visited array and recursion stack together need at most all cells.

8. Conclusion

By storing each island’s cells relative to its first cell, we turn a 2-D shape into a shift-invariant fingerprint. A simple DFS plus a Python set is enough to count how many unique fingerprints exist. This keeps the solution both fast (linear) and easy to understand.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.