How do you count the number of distinct islands in a non-empty 2D array of 0's and 1's, where islands are defined as groups of connected 1's (land) that can be translated but not rotated or reflected?

Approach When tasked with counting the number of distinct islands in a 2D array of 0's and 1's, a systematic approach is essential. Here’s a structured framework to tackle this problem: Understand the Problem : Clearly define what constitutes an island. An…

Approach

When tasked with counting the number of distinct islands in a 2D array of 0's and 1's, a systematic approach is essential. Here’s a structured framework to tackle this problem:

1. Understand the Problem: Clearly define what constitutes an island. An island is a group of connected 1's (land) that can be translated but cannot be rotated or reflected.
2. Data Structure Choice: Choose appropriate data structures to hold the array and possibly the unique shapes of the islands.
3. Traversal Method: Decide on a method for traversing the 2D array, such as Depth-First Search (DFS) or Breadth-First Search (BFS).
4. Shape Normalization: Normalize the shape of each island to ensure that different translations of the same island are counted as one.
5. Store Unique Shapes: Use a set to keep track of unique island shapes.
6. Count and Return: Finally, return the count of unique shapes stored in the set.

Key Points

• Definition of Island: Islands are groups of adjacent 1's connected vertically or horizontally.
• Shape Normalization: Essential for ensuring that different translations of the same island are recognized as identical.
• Data Structures: Utilize sets for storing unique shapes to leverage their properties for quick look-up and insertion.
• Traversal Techniques: Familiarize yourself with both DFS and BFS approaches to navigate through the matrix.

Standard Response

Here’s a comprehensive sample answer detailing the process of counting distinct islands in a 2D array of 0's and 1's:

def numDistinctIslands(grid):
 if not grid:
 return 0
 
 visited = set()
 unique_islands = set()

 def dfs(r, c, origin_r, origin_c, shape):
 if (r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or 
 grid[r][c] == 0 or (r, c) in visited):
 return
 
 visited.add((r, c))
 shape.append((r - origin_r, c - origin_c)) # Normalize shape

 dfs(r + 1, c, origin_r, origin_c, shape) # down
 dfs(r - 1, c, origin_r, origin_c, shape) # up
 dfs(r, c + 1, origin_r, origin_c, shape) # right
 dfs(r, c - 1, origin_r, origin_c, shape) # left

 for r in range(len(grid)):
 for c in range(len(grid[0])):
 if grid[r][c] == 1 and (r, c) not in visited:
 shape = []
 dfs(r, c, r, c, shape) # Start DFS
 unique_islands.add(tuple(shape)) # Store as tuple to add to set

 return len(unique_islands)

Tips & Variations

Common Mistakes to Avoid

• Ignoring Edge Cases: Always consider edge cases, such as completely empty grids.
• Failing to Normalize Shapes: If shapes are not normalized, distinct islands may be incorrectly counted.
• Using Mutable Data Structures: When adding shapes to sets, ensure they are immutable (e.g., convert lists to tuples).

Alternative Ways to Answer

• BFS Approach: Instead of DFS, a BFS approach can also be implemented, especially in languages or environments where recursion depth is a concern.