Problem Description

You have a 2D binary grid where 1 represents land and 0 represents water. Connected 1s that are adjacent horizontally or vertically form an island. The grid is surrounded by water on all four edges.

The key challenge is to count how many distinct island shapes exist in the grid. Two islands are considered the same if one can be moved (translated) to exactly match the other. You cannot rotate or flip the islands - only sliding them to different positions is allowed.

For example, these two islands would be considered the same:

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

The second island is just the first one translated to a different position.

The solution uses DFS to explore each island and records the traversal path. By encoding the direction of each DFS step (up, down, left, right), it creates a unique signature for each island shape. When the DFS enters a cell, it records the direction taken, and when it backtracks, it records the negative of that direction. This creates a unique string representation for each distinct island shape.

The dfs function marks visited cells as 0 and builds a path string. The parameter k represents the direction taken to reach the current cell (1 for up, 2 for right, 3 for down, 4 for left, 0 for starting point). By storing these paths in a set, duplicate island shapes are automatically filtered out, and the final answer is the size of this set.

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 cells with value 1 (land) are connected horizontally and vertically to form islands. This is essentially a graph where each cell is a node and adjacent cells form edges.

Is it a tree?

• No: The grid structure is not a tree. It's a 2D grid that can have multiple disconnected components (islands), and within each island, there could be cycles when cells form loops.

Is the problem related to directed acyclic graphs?

• No: The grid represents an undirected graph where connections between adjacent land cells are bidirectional.

Is the problem related to shortest paths?

• No: We're not finding shortest paths between points. We need to identify and compare island shapes.

Does the problem involve connectivity?

• Yes: The core of the problem is about connectivity - finding connected components (islands) of 1s in the grid and determining their distinct shapes.

Does the problem have small constraints?

• Yes: While not explicitly stated, grid problems typically have manageable constraints that allow for traversal-based solutions.

Brute force / Backtracking?

• Yes: We need to explore each island completely using DFS/backtracking to record its shape pattern. The DFS traversal with backtracking helps us create a unique signature for each island shape.

Conclusion: The flowchart leads us to use DFS/backtracking approach. This aligns perfectly with the solution, which uses DFS to traverse each island while recording the traversal path to create a unique signature for each distinct island shape.

Intuition

When we need to identify distinct island shapes, the main challenge is determining when two islands have the same shape but are just positioned differently in the grid.

Think about how you would describe an island's shape to someone who can't see it. You might say: "Start at a cell, go right, then down, then right again, then up..." This sequence of moves uniquely defines the shape! If two islands have the same sequence of moves when traversed in the same manner, they must have the same shape.

The key insight is that we can create a "signature" for each island by recording the path we take during DFS traversal. But here's the clever part: we need to record not just that we visited cells, but how we moved between them.

Consider these two identical L-shaped islands:

Island 1:    Island 2:
1 1          0 1 1
1 0          0 1 0

If we start DFS from the top-left of each and record directions (Right, Down), both produce the same pattern, confirming they're the same shape.

However, simply recording forward movements isn't enough. We also need to track when we backtrack, because backtracking patterns are also part of what makes each shape unique. For instance, after exploring a dead-end branch, we return to explore other branches - this backtracking behavior differs between shapes.

By encoding each forward move with a direction number (1=up, 2=right, 3=down, 4=left) and each backtrack with its negative, we create a complete traversal signature. Two islands with the same shape will always produce the same signature when traversed from their respective "starting points" (first encountered cell), regardless of where they're positioned in the grid.

This transforms our shape comparison problem into a simple string matching problem - we just need to count unique signature strings!

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

Solution Approach

The implementation uses DFS with path encoding to create unique signatures for each island shape. Let's walk through the key components:

Main Loop Structure:

for i, row in enumerate(grid):
    for j, x in enumerate(row):
        if x:  # Found a new island (cell with value 1)
            dfs(i, j, 0)
            paths.add("".join(path))
            path.clear()

We iterate through each cell in the grid. When we find a 1 (land), we start a DFS from that cell to explore the entire island.

DFS Function:

def dfs(i: int, j: int, k: int):
    grid[i][j] = 0  # Mark as visited
    path.append(str(k))  # Record the direction we came from

The DFS function takes three parameters:

• i, j: current cell coordinates
• k: the direction taken to reach this cell (0 for starting point, 1-4 for up/right/down/left)

Direction Exploration:

dirs = (-1, 0, 1, 0, -1)
for h in range(1, 5):
    x, y = i + dirs[h - 1], j + dirs[h]
    if 0 <= x < m and 0 <= y < n and grid[x][y]:
        dfs(x, y, h)

The dirs array is a compact way to represent four directions:

• h=1: up (dx=-1, dy=0)
• h=2: right (dx=0, dy=1)
• h=3: down (dx=1, dy=0)
• h=4: left (dx=0, dy=-1)

For each valid neighboring land cell, we recursively call DFS, passing the direction h as the parameter.

Backtracking Marker:

path.append(str(-k))  # Add negative direction when backtracking

After exploring all neighbors from a cell, we append the negative of the incoming direction. This marks the backtracking step and is crucial for distinguishing different shapes.

Using a Set for Uniqueness:

paths = set()
paths.add("".join(path))
return len(paths)

We use a set to store the path signatures. Since sets automatically handle duplicates, islands with identical shapes (same path signatures) will only be counted once.

Example Path Generation: For an L-shaped island:

1 1
1 0

Starting from top-left, the path might be: "0,2,2,-2,3,3,-3,-0"

• 0: start
• 2: move right
• 2,-2: explore and backtrack from top-right
• 3: move down
• 3,-3: explore and backtrack from bottom-left
• -0: backtrack from start

This string uniquely identifies the L-shape, and any other L-shaped island in the grid will generate the exact same string.

Example Walkthrough

Let's walk through a small example to illustrate how the solution identifies distinct island shapes.

Consider this 4×5 grid:

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

This grid contains 3 islands. Let's trace through how the algorithm processes each one.

Island 1 (top-left corner):

1 1
1 0

Starting DFS from position (0,0):

1. Start at (0,0), append "0" to path (starting point)
2. Explore right to (0,1), append "2" (moved right)
3. No valid neighbors from (0,1), backtrack, append "-2"
4. Back at (0,0), explore down to (1,0), append "3" (moved down)
5. No valid neighbors from (1,0), backtrack, append "-3"
6. Back at (0,0), done exploring, append "-0" (backtrack from start)

Final path: "0 2 -2 3 -3 -0" → This represents an L-shape

Island 2 (top-right corner):

1 1
1 0

Starting DFS from position (0,3):

1. Start at (0,3), append "0" to path
2. Explore right to (0,4), append "2"
3. No valid neighbors from (0,4), backtrack, append "-2"
4. Back at (0,3), explore down to (1,3), append "3"
5. No valid neighbors from (1,3), backtrack, append "-3"
6. Back at (0,3), done exploring, append "-0"

Final path: "0 2 -2 3 -3 -0" → Same as Island 1! They're the same shape.

Island 3 (bottom row):

1 0 1 1

Starting DFS from position (3,0):

1. Start at (3,0), append "0" to path
2. No valid neighbors (isolated cell), append "-0"

Final path: "0 -0" → Single cell island

Then continuing from position (3,2):

1. Start at (3,2), append "0" to path
2. Explore right to (3,3), append "2"
3. No valid neighbors from (3,3), backtrack, append "-2"
4. Back at (3,2), done exploring, append "-0"

Final path: "0 2 -2 -0" → Horizontal line of 2 cells

Result: The algorithm found these unique paths:

• "0 2 -2 3 -3 -0" (L-shape, appears twice)
• "0 -0" (single cell)
• "0 2 -2 -0" (horizontal line)

Since we store paths in a set, duplicates are automatically removed. The set contains 3 unique signatures, so the answer is 3 distinct island shapes.

The beauty of this approach is that Islands 1 and 2, despite being in different positions, generate identical path signatures because they have the same shape. The path encoding captures the essential structure of each island independent of its position in the grid.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n)

The algorithm performs a depth-first search (DFS) on each cell of the grid. In the worst case, where the entire grid consists of land (all 1s forming one large island), the DFS will visit each cell exactly once. The outer loops iterate through all m * n cells, and for each unvisited land cell, DFS is initiated. Since each cell is visited at most once (marked as 0 after visiting), the total time complexity is O(m * n).

Space Complexity: O(m * n)

The space complexity consists of several components:

• Recursion Stack: In the worst case, the DFS recursion can go as deep as O(m * n) when the entire grid forms a single island with a snake-like pattern.
• Path List: The path list stores the traversal pattern for each island. In the worst case, for a single island covering the entire grid, the path list can contain up to O(m * n) elements (each cell contributes at least 2 entries: the direction entering and -direction when backtracking).
• Paths Set: The paths set stores unique string representations of islands. In the worst case, if every cell is a separate island, there could be O(m * n) unique islands, though each would have a small string representation. The total space for all strings combined is bounded by O(m * n).

Therefore, the overall space complexity is O(m * n).

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

Common Pitfalls

1. Forgetting the Backtracking Marker

One of the most common mistakes is omitting the negative direction marker (path.append(str(-direction))) when backtracking from a cell. This line is crucial for distinguishing between different island shapes.

Why it matters: Without the backtracking marker, different island shapes can generate identical path signatures.

Consider these two different shapes:

Shape A:     Shape B:
1 1 1        1 1
             1

Without backtracking markers:

• Shape A might generate: "0,2,2" (start, right, right)
• Shape B might generate: "0,2,3" (start, right, down)

With backtracking markers:

• Shape A generates: "0,2,2,-2,2,2,-2,-2,-0"
• Shape B generates: "0,2,2,-2,-2,3,3,-3,-0"

The backtracking markers ensure each unique shape has a unique signature.

2. Using Incorrect Direction Encoding

Another pitfall is inconsistent or incorrect direction encoding. The solution must use the same direction numbers (1=up, 2=right, 3=down, 4=left) consistently throughout the traversal.

Problem Example:

# Incorrect: Using different direction values or starting from 0
for h in range(4):  # This would use 0,1,2,3 instead of 1,2,3,4
    x, y = i + dirs[h], j + dirs[h + 1]
    if valid:
        dfs(x, y, h)  # Passing 0-based direction

Solution: Always use consistent 1-based indexing for directions as shown in the original code:

for h in range(1, 5):  # Use 1,2,3,4 for directions
    x, y = i + dirs[h - 1], j + dirs[h]
    if valid:
        dfs(x, y, h)

3. Not Clearing the Path Between Islands

Forgetting to clear the path list between different islands will cause all islands to be concatenated into a single signature.

Problem Example:

for i in range(rows):
    for j in range(cols):
        if grid[i][j] == 1:
            dfs(i, j, 0)
            unique_islands.add("".join(path))
            # Missing: path.clear()

This would create increasingly long strings that combine multiple islands, leading to incorrect results.

Solution: Always clear the path after processing each island:

if grid[i][j] == 1:
    dfs(i, j, 0)
    unique_islands.add("".join(path))
    path.clear()  # Essential for correctness

4. Modifying the Original Grid Without Consideration

The solution modifies the input grid by setting visited cells to 0. If the original grid needs to be preserved, this approach will destroy the input data.

Solution if preservation is needed: Create a separate visited array or restore the grid after processing:

# Option 1: Use a separate visited set
visited = set()

def dfs(row, col, direction):
    visited.add((row, col))
    # Check if (next_row, next_col) not in visited instead of grid value

# Option 2: Restore the grid
original_grid = [row[:] for row in grid]  # Deep copy
# ... perform algorithm ...
grid[:] = original_grid  # Restore if needed

5. Incorrect Boundary Checking

Off-by-one errors in boundary checking can cause index out of bounds errors or miss valid cells.

Problem Example:

# Incorrect: using <= for upper bounds
if 0 <= next_row <= rows and 0 <= next_col <= cols:

Solution: Use strict less-than for upper bounds:

if 0 <= next_row < rows and 0 <= next_col < cols: