LeetCode 694: Number of Distinct Islands Solution in Python – A Step-by-Step Guide

What Is LeetCode 694: Number of Distinct Islands?

In LeetCode 694: Number of Distinct Islands, you’re given a 2D binary grid where 1 represents land and 0 represents water, and your task is to count the number of distinct island shapes. An island is a group of connected 1s (horizontally or vertically), and two islands are distinct if their shapes differ, regardless of position or rotation—they must match exactly when translated. Return this count as an integer. For example, with grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]], there are two islands (both 2×2 squares), but they’re the same shape, so return 1. This problem tests your ability to identify and canonicalize shapes efficiently.

Problem Statement

• Input:
• grid: 2D list of integers (0s and 1s).
• Output: An integer—number of distinct island shapes.
• Rules:
• Island: Connected 1s (4-directional: up, down, left, right).
• Distinct: Same shape, not position/rotation (translation only).
• Count unique shapes, not total islands.

Constraints

• 1 ≤ grid.length, grid[0].length ≤ 50.
• grid[i][j] is 0 or 1.

Examples

• Input: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
• Output: 1 (Two 2×2 squares, same shape)
• Input: grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
• Output: 3 (Three distinct shapes)
• Input: grid = [[0,0],[0,0]]
• Output: 0 (No islands)

These examples set the grid—let’s solve it!

Understanding the Problem: Counting Distinct Islands

To solve LeetCode 694: Number of Distinct Islands in Python, we need to count unique island shapes in a grid, where islands are connected 1s, and distinctness depends on shape, not position. A brute-force approach—comparing all islands pairwise—would be O(n * m * (n * m)), inefficient for grids up to 50×50. Since we’re identifying shapes, DFS or BFS with a canonical representation (e.g., path or normalized coordinates) can optimize this by encoding each island uniquely. We’ll use:

• Best Solution (DFS with Canonical Path Encoding): O(n m) time, O(n m) space—fast and elegant.
• Alternative Solution (BFS with Shape Normalization): O(n m) time, O(n m) space—intuitive but more complex.

Let’s start with the DFS solution, breaking it down for beginners.

Best Solution: DFS with Canonical Path Encoding

Why This Is the Best Solution

The DFS with canonical path encoding approach is the top choice for LeetCode 694 because it’s highly efficient—O(n * m) time with O(n * m) space—and uses depth-first search to traverse each island, encoding its shape as a sequence of directional moves (e.g., up, down, left, right) from the starting point, ensuring translation invariance without complex normalization. It fits constraints (n, m ≤ 50) perfectly and is intuitive once you see the path logic. It’s like tracing each island’s outline with a unique signature!

How It Works

Think of this as an island tracer:

• Step 1: Define Directions:
• Moves: [(0, 1), (1, 0), (0, -1), (-1, 0)] (right, down, left, up).
• Step 2: DFS Function:
• Start at a 1, mark visited, record path (e.g., "r" for right).
• Recurse on 4 neighbors, append direction to path.
• Step 3: Process Grid:
• Scan grid, DFS on each unvisited 1, collect path strings.
• Step 4: Count Distinct:
• Use set to count unique path strings.
• Step 5: Return Result:
• Size of set (number of distinct shapes).

It’s like a path scribe—trace and count!

Step-by-Step Example

Example: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]

• Grid:
``` 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 ```
• Step 1: Directions: r(0,1), d(1,0), l(0,-1), u(-1,0).
• Step 2: DFS:
• Start (0, 0):
• Path: "", visit (0, 0).
• Right (0, 1): "r", visit.
• Down (1, 0): "d", visit (1, 0).
• Right (1, 1): "dr", visit.
• Shape: "rdr".
• Start (2, 3):
• Path: "", visit (2, 3).
• Right (2, 4): "r", visit.
• Up (1, 3): "d", visit (1, 3) (no, already visited elsewhere).
• Down (3, 3): "rd", visit.
• Right (3, 4): "rdr", visit.
• Shape: "rdr".
• Step 3: Paths: ["rdr", "rdr"].
• Step 4: Set: {"rdr"}, size = 1.
• Step 5: Return 1.
• Output: 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        # Step 1: Define directions
        directions = [(0, 1, 'r'), (1, 0, 'd'), (0, -1, 'l'), (-1, 0, 'u')]
        m, n = len(grid), len(grid[0])

        # Step 2: DFS to encode island shape
        def dfs(i: int, j: int, path: list) -> None:
            grid[i][j] = 0  # Mark visited
            for di, dj, direction in directions:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
                    path.append(direction)
                    dfs(ni, nj, path)

        # Step 3: Process grid and collect paths
        shapes = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    path = []
                    dfs(i, j, path)
                    shapes.add(''.join(path))

        # Step 4: Count distinct shapes
        return len(shapes)

• Line 4: Directions: Define moves with labels.
• Lines 7-13: DFS:
• Mark cell, explore 4 directions, append direction to path.
• Lines 16-23: Process:
• Scan grid, DFS on 1s, collect unique path strings in set.
• Line 26: Return: Size of shapes set.
• Time Complexity: O(n * m)—visit each cell once.
• Space Complexity: O(n * m)—visited cells and path storage.

This is like an island signer—trace and hash!

Alternative Solution: BFS with Shape Normalization

Why an Alternative Approach?

The BFS with shape normalization approach uses breadth-first search—O(n * m) time, O(n * m) space. It’s more intuitive for some, exploring islands level-by-level and normalizing coordinates to a canonical form, but requires extra steps to ensure shape uniqueness. It’s like mapping each island and shifting it to a standard corner!

How It Works

Picture this as an island mapper:

• Step 1: BFS to find islands:
• Queue cells, collect coordinates.
• Step 2: Normalize shape:
• Shift all coordinates by min row/col to (0, 0).
• Step 3: Count distinct:
• Use set of normalized coordinate tuples.
• Step 4: Return result.

It’s like a shape shifter—queue and normalize!

Step-by-Step Example

Example: Same as above

• Step 1: BFS:
• Island 1: (0,0), (0,1), (1,0), (1,1).
• Island 2: (2,3), (2,4), (3,3), (3,4).
• Step 2: Normalize:
• Island 1: Min (0,0) → [(0,0), (0,1), (1,0), (1,1)].
• Island 2: Min (2,3) → [(0,0), (0,1), (1,0), (1,1)].
• Step 3: Set: {((0,0), (0,1), (1,0), (1,1))}, size = 1.
• Step 4: Return 1.
• Output: 1.

Code for BFS Approach

from collections import deque

class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        # Step 1: BFS to find island coordinates
        def bfs(i: int, j: int) -> set:
            queue = deque([(i, j)])
            coords = set([(i, j)])
            grid[i][j] = 0
            while queue:
                r, c = queue.popleft()
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                        queue.append((nr, nc))
                        coords.add((nr, nc))
                        grid[nr][nc] = 0
            return coords

        # Step 2: Normalize and collect shapes
        shapes = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    coords = bfs(i, j)
                    # Normalize to (0, 0)
                    min_r = min(r for r, _ in coords)
                    min_c = min(c for _, c in coords)
                    normalized = tuple(sorted((r - min_r, c - min_c) for r, c in coords))
                    shapes.add(normalized)

        # Step 3: Return distinct count
        return len(shapes)

• Line 1: Import deque.
• Lines 5-6: Define directions.
• Lines 9-20: BFS:
• Queue cells, collect coordinates, mark visited.
• Lines 23-33: Normalize:
• BFS for coords, shift to (0,0), add to set.
• Line 36: Return: Size of shapes set.
• Time Complexity: O(n * m)—visit each cell once.
• Space Complexity: O(n * m)—queue and set.

It’s a shape normalizer—queue and shift!

Comparing the Two Solutions

• DFS (Best):
• Pros: O(n m) time, O(n m) space, simple and efficient.
• Cons: Path encoding less obvious.
• BFS (Alternative):
• Pros: O(n m) time, O(n m) space, clear level-wise.
• Cons: Normalization more complex.

DFS wins for simplicity.

Additional Examples and Edge Cases

• Input: grid = [[1]]
• Output: 1.
• Input: grid = [[0]]
• Output: 0.

DFS handles these well.

Complexity Breakdown

• DFS: Time O(n m), Space O(n m).
• BFS: Time O(n m), Space O(n m).

DFS is optimal for ease.

Key Takeaways

• DFS: Path encoding—smart!
• BFS: Shape normalizing—clear!
• Islands: Mapping is fun.
• Python Tip: DFS rocks—see Python Basics.

Final Thoughts: Chart Those Islands

LeetCode 694: Number of Distinct Islands in Python is a fun grid challenge. DFS with canonical path encoding offers speed and elegance, while BFS with shape normalization provides a clear alternative. Want more? Try LeetCode 200: Number of Islands or LeetCode 463: Island Perimeter. Ready to explore? Head to Solve LeetCode 694 on LeetCode and count those distinct islands today!