Problem Description

In this problem, you are given a binary matrix grid, representing a map where 1s indicate land, and 0s represent water. An island is defined as a contiguous group of 1s that are directly connected horizontally or vertically. The task is to determine the number of distinct islands in the grid.

However, there's a twist. Two islands are considered the same if one can be transformed into the other through rotation (90, 180, or 270 degrees) or reflection (flipping over a horizontal or vertical line). We are not simply counting the islands, but we are identifying distinct shapes of islands considering these transformations.

The goal is to return the total number of unique island shapes that exist in the given grid, taking into account the possible rotations and reflections that might make two seemingly different islands actually the same.

Flowchart Walkthrough

To analyze LeetCode 711. Number of Distinct Islands II, let's utilize the algorithm flowchart available at the Flowchart. Below is a detailed step-by-step examination of the problem through the flowchart's lens:

Is it a graph?

• Yes: The grid in the problem can be considered a graph where each cell represents a node, and edges are present between adjacent cells depending on their value (in this case, lands represented by '1').

Is it a tree?

• No: The structure being analyzed is not necessarily hierarchical like a tree; it consists possibly of multiple connected components each forming an island.

Is the problem related to directed acyclic graphs (DAGs)?

• No: The problem is focused on identifying islands and does not involve directed edges or acyclic structures.

Is the problem related to shortest paths?

• No: The goal is to count distinct islands after considering various transformations, not to find a path between points.

Does the problem involve connectivity?

• Yes: The key part of the problem is determining connected components (islands) and differentiating distinct ones based on transformations.

Does the problem require considering whether the graph is weighted?

• No: Since the problem deals with connectivity in an unweighted manner, where cells are simply either land or water.

Should we consider disjoint set union or other methodologies due to connectivity?

• No: While the problem involves connectivity, it's specific to analyzing the makeup and layout of connected components rather than simply connecting components. The need to identify and transform islands suggests a more active and detailed inspection of the structure of each island than what a Disjoint Set Union typically offers.

Does the problem have small constraints, suggesting that a DFS or backtracking approach might be feasible?

• Yes: Given that the problem input sizes (grid dimensions) are typically contained, it allows for a complete exploration approach like DFS or backtracking to track not only the presence of an island but also to handle transformations and compare structure.

Conclusion: Based on the flowchart, Depth-First Search (DFS) is a highly suitable method to address this problem. DFS is ideal for thoroughly exploring each island to record its structure, which can then be transformed and compared to other islands to count distinct types effectively.

Intuition

To approach this problem, we focus on identifying all islands first, and then transform each island into a canonical form that represents its shape. By comparing these canonical shapes, we can determine which islands are unique.

We use a Depth-First Search (DFS) algorithm to explore the grid and identify each island. Starting at a cell with a 1, we perform DFS to visit all land cells that are part of the same island. While visiting, we mark the cells as 0 to avoid revisiting and to help in identifying separate islands.

Once we have an island, the key challenge is determining its unique shape. We generate all possible rotations and reflections of the shape, normalize them by sorting and shifting to have the top-left coordinate at (0,0), and then choose the smallest one in sorted order as the canonical representative of that shape.

We store these canonical representatives in a set to automatically handle the uniqueness aspect—since sets only store unique items, any duplicate shapes will be ignored.

The final count of distinct islands is the size of this set, as it only contains unique shapes.

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

Solution Approach

The solution utilizes Depth-First Search (DFS) for graph traversal, set data structure to keep track of unique islands, and normalizes the islands for comparison.

1. Depth-First Search (DFS): The dfs function takes in the starting cell (i, j) along with a shape list that accumulates the cells that form part of the current island. Each call to dfs visits a new land cell, marks it as 0 by overwriting grid[i][j] to prevent revisiting, and recursively explores the four adjacent cells (up, down, left, right) for further land cells.

2. Normalization: The normalization process takes the shape of an island obtained from the dfs and generates all possible rotations and reflections. This is done by permuting the cell coordinates (i, j) as described in the code (e.g., shapes[0].append([i, j]) for the original shape, shapes[1].append([i, -j]) for a reflection, etc.). The 8 different transformations correspond to 4 rotations (0, 90, 180, 270 degrees) and their mirrored reflections.

3. Canonical Representation: After generating all transformations of an island's shape, each transformation is sorted to place the cells in a consistent order. Then, the coordinates are adjusted by subtracting the coordinates of the first cell (e[0][0], e[0][1]) from all cells to ensure that the 'top-left' cell of the shape is brought to (0,0). Among all permutations, the lexicographically smallest is selected as the canonical shape.

4. Unique Shapes: To determine the distinct islands, we store the canonical representations in a set s. Since a set naturally eliminates duplicates, adding the normalized shape of each island to the set helps us in only keeping unique islands.

5. Counting Distinct Islands: After iterating over every cell in the grid and performing the above steps for each 1 encountered, the number of distinct islands is simply the number of entries in the set s, which can be returned as len(s).

To sum up, the algorithm performs DFS to identify islands, uses permutations and sorting to normalize shapes, and leverages a set to count distinct islands, taking care of rotations and reflections without explicitly comparing each pair of islands. The resulting algorithm efficiently finds and groups islands with identical shapes, satisfying the conditions posed by the problem.

Example Walkthrough

Let's use a small 3x4 grid example to illustrate the solution approach:

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

This grid contains three pieces of land. However, not all these land parcels are distinct islands based on the given problem's criteria of rotations and reflections. Let's walk through the solution step by step, as outlined in the problem's solution approach.

1. We start with the Depth-First Search (DFS) at the top left of the grid. The DFS will identify the first island (top-left corner) and mark it visited by setting those 1s to 0s:

grid after DFS = [
    [0, 0, 0, 0],
    [0, 0, 0, 1],
    [1, 0, 0, 1]
]

• The shape list for this island will be [(0,0), (0,1), (1,1)].

2. The algorithm then generates all rotations and reflections of the shape list to obtain a set of potentially unique shapes:

• Original shape: [(0,0), (0,1), (1,1)]
• Rotate 90 degrees: [(0,0), (1,0), (1,-1)]
• Rotate 180 degrees: [(0,0), (0,-1), (-1,-1)]
• Rotate 270 degrees: [(0,0), (-1,0), (-1,1)]
• Reflect horizontally: [(0,0), (0,-1), (1,-1)]
• And more reflections from the above rotations.

3. The canonical representation would normalize these shapes and select the lexicographically smallest one. This often means the coordinates are shifted so that the first cell in all permutations is at (0,0), and then sorted. Let's assume the canonical shape for the first island is [(0,0), (0,-1), (1,-1)].

4. Now, we move to the next unvisited cell with a 1, at (1,3), and repeat the process of DFS to mark it visited, finding the second distinct island:

grid after the second DFS = [
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [1, 0, 0, 0]
]

• The shape list for the second island will be [(1,3)].

5. Since it's a single cell, all rotations and reflections will give the same shape list, which is already in its smallest canonical form.

6. The third island at (2,0) will yield the same shape list as the second island after going through DFS, rotations, reflections, and normalization. So, its canonical shape is [(0,0)].

7. Throughout, we add these canonical forms to a set to track unique shapes. Once we've visited all cells, the set will contain:

{
    [(0,0), (0,-1), (1,-1)],  // Canonical form of the first island
    [(0,0)]  // Canonical form of the second (and third) island
}

8. The final count of distinct islands for our example is the size of this set s, which is 2. Thus, the algorithm would return 2 for this example grid.

In conclusion, through DFS, normalizing with rotations and reflections, and using a set to keep track of unique island shapes, the algorithm effectively identifies the number of distinct islands in the grid.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code can be broken down as followed:

1. DFS (dfs function) traversal for every island: The DFS function may visit each cell in the grid up to 8 times due to considering all permutations of rotations and reflections (since normalize will iterate over all possible transformations). The outer loop (nested loop over grid) will go through all cells m * n, but an individual cell belongs to at most one island and once it's part of an island, it is marked as visited (grid[i][j] = 0). Thus, every cell is part of the DFS process at most once, so the complexity of this portion is O(m * n).

2. Normalization (normalize function) and addition to the set: For each island found, we create up to 8 normalized shapes. Each shape is then sorted, which takes O(k log k) time where k is the number of cells in a given island. This is multiplied by 8 (for the 8 shapes), and the complexity for each island is O(8 * k log k). However, since k can be at most m * n, and each cell is processed exactly once, if we sum it up for all islands, the upper bound across the entire grid remains O(m * n log (m * n)).

3. Sorting the normalized shapes: This is part of the normalization but sorting the list of shapes for an island contributes O(8 log 8) time, which is constant and can be simplified to O(1).

4. Operations for the set: Each normalized shape is added to a set. Assuming a good hash function with few collisions, this operation can be considered O(1) on average for each shape. Since there's a bounded number of unique shapes we can have, this does not significantly contribute to the overall time complexity.

Combining these points, the overall time complexity of the algorithm is dominated by the DFS and normalization steps, giving O(m * n log (m * n)).

Space Complexity

The space complexity can be analyzed as follows:

• Grid alteration: The input grid is modified in place, so there is no additional space needed proportional to the size of the grid.

• Recursive stack: In the worst case, the recursive stack for DFS can go as deep as the size of the grid if the grid is one large island, which is O(m * n).

• Shape storage: Shapes are stored, and their size can be up to the full size of the grid in a pathological case where the entire grid is one island, which also takes O(m * n) space.

• Set of islands: The number of unique shapes is stored, and while there could be a large number of permutations, they are ultimately constrained by the grid size. So the space taken up by all unique shapes in the set is O(m * n).

As a result, the overall space complexity is O(m * n) due to the storage of the shapes, the set of unique shapes, and the recursion stack for DFS.

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