694. Number of Distinct Islands - Detailed Explanation

Problem Statement

Description:
You are given a 2D grid of integers (0’s and 1’s) where:

• 1 represents land.
• 0 represents water.

An island is a group of connected 1’s (land cells) connected horizontally or vertically. Two islands are considered the same if and only if one island can be translated (moved horizontally and vertically) to match the other exactly. Your goal is to determine how many distinct islands exist in the grid.

Example 1:

• Input:

  grid = [
    [1,1,0,0,0],
    [1,0,0,0,0],
    [0,0,0,1,1],
    [0,0,0,1,1]
  ]
  

• Output: 1
• Explanation:
  There are two islands in the grid. One island is at the top-left and the other at the bottom-right. Although they are in different positions, their shapes are identical if you translate the top-left island to the bottom-right (both form an “L” shape).

Example 2:

• Input:

  grid = [
    [1,1,0,1,1],
    [1,0,0,0,0],
    [0,0,0,0,1],
    [1,1,0,1,1]
  ]
  

• Output: 3
• Explanation:
  The grid contains multiple islands with different shapes. After translating each island to a canonical position (using relative coordinates), you will find three distinct shapes.

Constraints:

• The dimensions of the grid can be up to around 50×50 (or similar constraints).
• The grid contains only 0’s and 1’s.
• Two islands are considered the same if one can be translated to match the other exactly.

Hints

• Hint 1:
  Think about how you can capture the shape of an island regardless of its position. A common technique is to record the relative positions of each cell in the island compared to a starting point (for example, the top-left cell of that island).

• Hint 2:
  Use a Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse each island. As you explore, record each cell’s relative coordinate (e.g., (row - start_row, col - start_col)).

• Hint 3:
  Once you have the relative positions for an island, you can convert the list of coordinates into a tuple (or another immutable data structure) and add it to a set. The size of the set will then give you the number of distinct island shapes.

Approach 1: Depth-First Search (DFS) with Relative Coordinates

Idea

1. Traverse the Grid:
   Iterate over every cell in the grid. When you find a cell with value 1 (land) that has not been visited, start a DFS from that cell.

2. Record Relative Positions:
   For the DFS, record the relative positions of each land cell in the island relative to the starting cell. For example, if the starting cell is at (i, j) and you visit a cell at (i + 2, j - 1), record the coordinate (2, -1).

3. Mark Visited Cells:
   As you traverse the island, mark the cells as visited (or change them to 0) to avoid reprocessing.

4. Store the Island Shape:
   Convert the list of relative positions to an immutable object (like a tuple of tuples) and insert it into a set. This ensures that duplicate shapes are not counted more than once.

5. Count Distinct Shapes:
   The number of elements in the set is the number of distinct island shapes.

Walkthrough Example

Consider the grid:

[
  [1,1,0,0],
  [1,0,0,0],
  [0,0,1,1],
  [0,0,1,1]
]

• Start at cell (0,0):
  • Begin DFS with starting point (0,0). Record (0,0) for cell (0,0).
  • Visit (0,1): record (0,1).
  • Visit (1,0): record (1,0).
  • The resulting relative shape is {(0,0), (0,1), (1,0)}.
• Later, when processing the bottom-right island, start at (2,2):

  • Record (0,0) for cell (2,2), (0,1) for (2,3), (1,0) for (3,2), and (1,1) for (3,3).

  • The shape is {(0,0), (0,1), (1,0), (1,1)}.

• If islands can be translated to match, you will only count those with identical relative positions. In this example, if both islands had the same relative structure, they would count as one. (The given example shows distinct shapes, so the set size would reflect the correct count.)

Code Implementation

Python Code