Problem Description

You have an m x n binary matrix grid where 1 represents land and 0 represents water. An island is formed by connecting adjacent lands horizontally or vertically (4-directionally connected). The entire grid is surrounded by water.

The key challenge is identifying distinct islands. Two islands are considered the same if:

• They have the exact same shape, OR
• One can be transformed into the other through:
  • Rotation: 90°, 180°, or 270° rotations
  • Reflection: flipping horizontally (left/right) or vertically (up/down)

Your task is to count how many distinct island shapes exist in the grid.

For example, if you have an L-shaped island and another island that looks like a rotated L, they count as the same shape (only 1 distinct island). Similarly, if one island is a mirror image of another, they're also considered the same.

The solution uses DFS to find all cells belonging to each island, then normalizes each island's shape by generating all 8 possible transformations (4 rotations × 2 reflections). By comparing the canonical form of each island shape, duplicate shapes are eliminated using a set, giving us the count of truly distinct islands.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a 2D grid where we need to explore connected components (islands). Each cell can be viewed as a node, and adjacent cells (4-directionally) form edges. Islands are essentially connected components in this implicit graph.

Is it a tree?

• No: The grid structure is not a tree. It's a general graph where we have multiple disconnected components (islands), and the structure doesn't follow parent-child relationships like a tree.

Is the problem related to directed acyclic graphs?

• No: The problem doesn't involve directed edges or acyclic properties. We're dealing with an undirected graph where connections between land cells are bidirectional.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between points. Instead, we need to identify and explore all cells belonging to each island to determine their shapes.

Does the problem involve connectivity?

• Yes: The core of the problem is about connectivity - we need to find all connected components (islands) of 1s in the grid and identify their distinct shapes.

Does the problem have small constraints?

• Yes: While not explicitly stated, grid problems typically have manageable constraints that allow for exploration algorithms. We need to explore each island completely to capture its shape.

DFS/backtracking?

• Yes: DFS is perfect for exploring each island completely. Starting from any land cell, we recursively visit all connected land cells to capture the complete shape of the island.

Conclusion: The flowchart suggests using DFS (Depth-First Search) to explore connected components in the grid. DFS allows us to traverse each island completely, recording all cell positions to determine the island's shape for comparison with other islands after normalization.

Intuition

When we look at this problem, the first challenge is understanding what makes two islands "the same." If we only cared about exact matches, we could simply record each island's shape and compare them directly. But since islands can be rotated or reflected and still be considered identical, we need a way to handle all these transformations.

Think about it like puzzle pieces - if you have two L-shaped pieces, one might be rotated 90° from the other, but they're still the same piece. The key insight is that for any given shape, there are exactly 8 possible orientations when considering all rotations and reflections:

• 4 rotations (0°, 90°, 180°, 270°)
• Each rotation can also be reflected (flipped)

So our strategy becomes: for each island we find, generate all 8 possible transformations of its shape. But we still need a consistent way to compare shapes. This is where normalization comes in.

The normalization process works by:

1. Taking all 8 transformations of an island's coordinates
2. Sorting each transformation to create a consistent ordering
3. Translating each shape so its "first" point is at origin (0, 0) - this makes the shape position-independent
4. Choosing the lexicographically smallest transformation as the "canonical" representation

By using DFS to explore each island and collect its coordinates, then normalizing these coordinates to a canonical form, we can use a set to automatically handle duplicates. Two islands that are the same shape (considering rotations and reflections) will have the same canonical form and thus be counted only once.

The beauty of this approach is that we don't need to explicitly check if two islands match through various transformations - the normalization process handles all of that automatically by reducing every possible variant of a shape to a single, unique representation.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The implementation uses DFS combined with a normalization technique to identify distinct islands. Let's walk through the key components:

1. DFS Exploration (dfs function)

The DFS function explores an entire island starting from a given cell (i, j):

• Records the current cell's coordinates in the shape list
• Marks the cell as visited by setting grid[i][j] = 0
• Recursively explores all 4 adjacent cells (up, down, left, right)
• Builds a complete list of coordinates representing the island's shape

def dfs(i, j, shape):
    shape.append([i, j])
    grid[i][j] = 0
    for a, b in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        x, y = i + a, j + b
        if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
            dfs(x, y, shape)

2. Shape Normalization (normalize function)

This is the core logic that handles rotations and reflections. For each island shape, it generates all 8 possible transformations:

shapes[0].append([i, j])      # Original
shapes[1].append([i, -j])     # Reflect horizontally
shapes[2].append([-i, j])     # Reflect vertically
shapes[3].append([-i, -j])    # Rotate 180°
shapes[4].append([j, i])      # Rotate 90° counter-clockwise
shapes[5].append([j, -i])     # Rotate 90° + reflect
shapes[6].append([-j, i])     # Rotate 270° + reflect
shapes[7].append([-j, -i])    # Rotate 270°

After generating all transformations:

• Each transformation is sorted to create consistent ordering
• Each shape is translated so its first point becomes (0, 0):

  for i in range(len(e) - 1, -1, -1):
      e[i][0] -= e[0][0]
      e[i][1] -= e[0][1]

• The lexicographically smallest transformation is chosen as the canonical form
• The result is converted to a tuple (immutable and hashable) for set storage

3. Main Algorithm

The main loop:

• Iterates through every cell in the grid
• When a land cell (1) is found, initiates DFS to explore the entire island
• Normalizes the island's shape to get its canonical representation
• Adds the canonical form to a set (automatically handles duplicates)
• Returns the size of the set, which gives the count of distinct islands

s = set()
for i in range(m):
    for j in range(n):
        if grid[i][j]:
            shape = []
            dfs(i, j, shape)
            s.add(normalize(shape))
return len(s)

The time complexity is O(m × n × k) where k is the average size of an island, as we need to normalize each island's shape. The space complexity is O(m × n) for storing island shapes and the set of canonical forms.

Example Walkthrough

Let's walk through a small example to illustrate how the solution identifies distinct islands:

Grid:
1 1 0 0 0
1 0 0 0 0
0 0 0 1 1
0 0 0 0 1

Step 1: Find First Island Starting at (0,0), we encounter a '1'. DFS explores the island:

• Visit (0,0), add to shape: [(0,0)]
• Visit (0,1), add to shape: [(0,0), (0,1)]
• Visit (1,0), add to shape: [(0,0), (0,1), (1,0)]
• Mark all visited cells as 0

Island 1 coordinates: [(0,0), (0,1), (1,0)] - This is an L-shape.

Step 2: Normalize First Island Generate all 8 transformations of [(0,0), (0,1), (1,0)]:

1. Original: [(0,0), (0,1), (1,0)]
2. Reflect H: [(0,0), (0,-1), (1,0)]
3. Reflect V: [(0,0), (0,1), (-1,0)]
4. Rotate 180°: [(0,0), (0,-1), (-1,0)]
5. Rotate 90° CCW: [(0,0), (1,0), (0,1)]
6. Rotate 90° + reflect: [(0,0), (-1,0), (0,1)]
7. Rotate 270° + reflect: [(0,0), (1,0), (0,-1)]
8. Rotate 270°: [(0,0), (-1,0), (0,-1)]

After sorting each transformation and translating to origin:

• Transform 1 sorted: [(0,0), (0,1), (1,0)] → After translation: [(0,0), (0,1), (1,0)]
• Transform 5 sorted: [(0,0), (0,1), (1,0)] → After translation: [(0,0), (0,1), (1,0)]
• (Other transforms produce different results)

Choose lexicographically smallest: ((0,0), (0,1), (1,0)) Add to set: {((0,0), (0,1), (1,0))}

Step 3: Find Second Island Starting at (2,3), we find another island:

• Visit (2,3), add to shape: [(2,3)]
• Visit (2,4), add to shape: [(2,3), (2,4)]
• Visit (3,4), add to shape: [(2,3), (2,4), (3,4)]

Island 2 coordinates: [(2,3), (2,4), (3,4)] - This is also an L-shape, but rotated!

Step 4: Normalize Second Island Original coordinates: [(2,3), (2,4), (3,4)]

First, let's look at what happens with just the relative positions (ignoring the actual positions):

• Relative to first point: [(0,0), (0,1), (1,1)]

Generate transformations:

1. Original: [(0,0), (0,1), (1,1)]
2. Rotate 90°: [(0,0), (1,0), (1,-1)]
3. Rotate 180°: [(0,0), (0,-1), (-1,-1)]
4. Rotate 270°: [(0,0), (-1,0), (-1,1)] ... and reflections

After normalization, one of the transformations (specifically a 270° rotation) produces:

• Sorted and translated: [(0,0), (0,1), (1,0)]

This canonical form ((0,0), (0,1), (1,0)) already exists in our set!

Step 5: Final Result Set remains: {((0,0), (0,1), (1,0))} Count of distinct islands: 1

Even though we found two islands in different orientations, the normalization process correctly identified them as the same shape, giving us the correct count of 1 distinct island.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n * k * log(k)) where m and n are the dimensions of the grid, and k is the size of the largest island.

• The outer loops iterate through all cells in the grid: O(m * n)
• For each cell that starts an island, we perform DFS which visits all cells in that island: O(k) where k is the island size
• The normalize function is called for each island:
  • Creating 8 transformations: O(8 * k) = O(k)
  • Sorting each of the 8 transformations: O(8 * k * log(k)) = O(k * log(k))
  • Normalizing coordinates by subtracting the first element: O(8 * k) = O(k)
  • Sorting the 8 transformations to find the canonical form: O(8 * log(8) * k) = O(k) (comparing lists of size k)
  • Converting to tuple: O(k)
  • Overall normalize: O(k * log(k))
• In the worst case where we have O(m * n / k) islands, the total time is: O((m * n / k) * k * log(k)) = O(m * n * log(k))
• However, when considering all operations including DFS traversal for all cells: O(m * n * k * log(k))

Space Complexity: O(m * n)

• The shape list stores coordinates for one island at a time: O(k) where k is the island size
• The shapes list in normalize stores 8 transformations: O(8 * k) = O(k)
• The set s stores unique normalized island shapes. In the worst case, every cell could be a separate island: O(m * n)
• The recursion stack depth for DFS can be at most O(m * n) in the worst case of a snake-like island
• Overall space complexity: O(m * n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Input Grid Without Restoration

The current solution modifies the input grid by setting visited cells to 0. This destructive approach can be problematic if:

• The grid needs to be preserved for other operations
• Multiple test cases run on the same grid instance
• The problem explicitly states not to modify the input

Solution: Use a separate visited set to track explored cells instead of modifying the grid:

def dfs(row: int, col: int, island_cells: List[List[int]], visited: Set[Tuple[int, int]]) -> None:
    island_cells.append([row, col])
    visited.add((row, col))
  
    for delta_row, delta_col in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        next_row = row + delta_row
        next_col = col + delta_col
        if (0 <= next_row < rows and 
            0 <= next_col < cols and 
            grid[next_row][next_col] == 1 and
            (next_row, next_col) not in visited):
            dfs(next_row, next_col, island_cells, visited)

# In main loop:
visited = set()
for row in range(rows):
    for col in range(cols):
        if grid[row][col] == 1 and (row, col) not in visited:
            island_cells = []
            dfs(row, col, island_cells, visited)
            unique_islands.add(normalize(island_cells))

2. Incorrect Transformation Logic

A subtle but critical pitfall is incorrectly implementing the 8 transformations. The transformations must correctly represent all possible rotations and reflections:

Common mistakes:

• Missing some transformations (e.g., only doing 4 instead of 8)
• Incorrect rotation formulas (mixing up clockwise vs counter-clockwise)
• Not handling both horizontal and vertical reflections

Solution: Verify transformations with a simple test case. For a point (x, y):

• 90° CCW rotation: (-y, x)
• 90° CW rotation: (y, -x)
• 180° rotation: (-x, -y)
• Horizontal reflection: (x, -y)
• Vertical reflection: (-x, y)

3. Inefficient Normalization Process

The current implementation sorts transformations multiple times and creates many intermediate lists, which can be memory-intensive for large islands.

Solution: Optimize by finding the canonical form more efficiently:

def normalize(island_cells: List[List[int]]) -> Tuple[Tuple[int, ...]]:
    def get_canonical(cells):
        # Sort and translate to origin in one pass
        cells = sorted(cells)
        if not cells:
            return tuple()
        base_row, base_col = cells[0]
        return tuple((r - base_row, c - base_col) for r, c in cells)
  
    # Generate and compare transformations without storing all of them
    min_shape = None
    for transform_func in [
        lambda r, c: (r, c),      # Original
        lambda r, c: (r, -c),     # Reflect y
        lambda r, c: (-r, c),     # Reflect x
        lambda r, c: (-r, -c),    # Rotate 180
        lambda r, c: (c, r),      # Rotate 90 CCW
        lambda r, c: (c, -r),     # Rotate 90 CCW + reflect
        lambda r, c: (-c, r),     # Rotate 270 CCW
        lambda r, c: (-c, -r),    # Rotate 270
    ]:
        transformed = [transform_func(r, c) for r, c in island_cells]
        canonical = get_canonical(transformed)
        if min_shape is None or canonical < min_shape:
            min_shape = canonical
  
    return min_shape

4. Stack Overflow with Large Islands

For very large islands, the recursive DFS can cause stack overflow.

Solution: Use iterative DFS with an explicit stack:

def dfs_iterative(start_row: int, start_col: int) -> List[List[int]]:
    island_cells = []
    stack = [(start_row, start_col)]
    visited.add((start_row, start_col))
  
    while stack:
        row, col = stack.pop()
        island_cells.append([row, col])
      
        for delta_row, delta_col in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            next_row = row + delta_row
            next_col = col + delta_col
            if (0 <= next_row < rows and 
                0 <= next_col < cols and 
                grid[next_row][next_col] == 1 and
                (next_row, next_col) not in visited):
                visited.add((next_row, next_col))
                stack.append((next_row, next_col))
  
    return island_cells