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.