Solution Explanation: Number of Distinct Islands II

This problem asks to find the number of distinct islands in a binary matrix, considering rotations and reflections as equivalent shapes. The solution involves Depth-First Search (DFS) to identify islands, and a normalization technique to handle shape equivalence.

Approach:

1. Island Identification (DFS): The solution uses DFS to traverse each connected component of 1s (representing land) in the grid. For each island, it records the relative coordinates of the cells within the island relative to the starting cell. This creates a shape representation for each island.

2. Shape Normalization: The crucial part is to normalize the shapes to account for rotations and reflections. The algorithm generates all eight possible transformations (4 rotations and 4 reflections) of a given island shape. It then sorts these transformations lexicographically, selecting the lexicographically smallest one as the canonical representation. This ensures that islands with the same shape, regardless of orientation, will have the same normalized representation.

3. Distinct Island Counting: The normalized shapes are stored in a set (in Python, Java, and C++) to automatically remove duplicates. The final count of unique shapes in the set gives the number of distinct islands.

Time Complexity Analysis:

• DFS: The DFS traversal visits each cell at most once, resulting in O(M*N) time complexity, where M and N are the dimensions of the grid.
• Normalization: Generating all eight transformations of a shape takes O(K log K) time, where K is the number of cells in the island. Sorting the transformations takes O(8K log K), which simplifies to O(K log K). Since K is at most MN, this step has a maximum time complexity of O(MN log(M*N)).
• Set Operations: Inserting into and checking the size of a set takes O(K log S) on average, where S is the number of elements in the set. In the worst case (all islands have the same shape after normalization), S can be O(MN). Thus, set operations contribute O(MN log(M*N)) time in the worst case.

Therefore, the overall time complexity is dominated by the DFS and normalization steps, resulting in O(MN log(MN)) time complexity.

Space Complexity Analysis:

• DFS: The space used by the recursive calls of DFS is proportional to the maximum depth of the recursion, which is at most min(M, N). Therefore, space used by DFS is O(min(M,N)).
• Shape Storage: Storing island shapes requires space proportional to the total number of cells in all islands, which is at most O(M*N).
• Set: The set stores normalized shapes, which also takes at most O(M*N) space in the worst case.

Hence, the overall space complexity is O(M*N).

Code Examples (with detailed comments):

The provided code snippets in Python, Java, and C++ implement the above approach. The key functions are dfs (for DFS traversal), normalize (for shape normalization), and the main function (numDistinctIslands2) to orchestrate the process. The normalization functions handle the generation of all possible transformations and the sorting to achieve unique representation of island shapes. The use of sets efficiently handles the deduplication of normalized shapes.