694. Number of Distinct Islands

Problem Description

In this problem, we are tasked to find the number of distinct islands on a given m x n binary grid. Each cell in the grid can either be "1" (representing land) or "0" (representing water). An island is defined as a group of "1"s connected horizontally or vertically. We are also told that all the edges of the grid are surrounded by water, which simplifies the problem by ensuring we don't need to handle edge scenarios where islands might be connected beyond the grid.

To consider two islands as the same, they have to be identical in shape and size, and they must be able to be translated (moved horizontally or vertically, but not rotated or flipped) to match one another. The objective is to return the number of distinct islands—those that are not the same as any other island in the grid.

Intuition

The solution leverages a Depth-First Search (DFS) approach. The core idea is to explore each island, marking the visited 'land' cells, and record the paths taken to traverse each island uniquely. These paths are captured as strings, which allows for easy comparison of island shapes.

Here's the step-by-step intuition behind the approach:

1. Iterate through each cell in the grid.
2. When land ("1") is found, commence a DFS from that cell to visit all connected 'land' cells of that island, effectively marking it to avoid revisiting.
3. While executing DFS, record the direction taken at each step to uniquely represent the path over the island. This is done using a representative numerical code.
4. Append reverse steps at the end of each DFS call to differentiate between paths when the DFS backtracks. This ensures that shapes are uniquely identified even if they take the same paths but in different order.
5. After one complete island is traversed and its path is recorded, add the path string to a set to ensure we only count unique islands.
6. Clear the path and continue the search for the next unvisited 'land' cell to find all islands.
7. After the entire grid is scanned, count the number of unique path strings in the set, which corresponds to the number of distinct islands.

This solution is efficient and elegant because the DFS ensures that each cell is visited only once, and the set data structure automatically handles the uniqueness of the islands.

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

Solution Approach

The implementation of the solution can be broken down into several key components, using algorithms, data structures, and patterns which are encapsulated in the DFS strategy outlined previously:

1. Depth-First Search (DFS):

   • This recursive algorithm is essential for traversing the grid and visiting every possible 'land' cell in an island once. The DFS is initiated whenever a '1' is encountered, and it continues until there are no more adjacent '1's to visit.

2. Grid Modification to Mark Visited Cells:

   • As the DFS traverses the grid, it marks the cells that have been visited by flipping them from '1' to '0'. This prevents revisiting the same cell and ensures each 'land' cell is part of only one island.

3. Directions and Path Encoding:

   • Four possible directions for movement are captured in a list of deltas dirs. During DFS, the current direction taken is recorded by appending a number to the path list, which is converted to a string for easy differentiation.

4. Backtracking with Signature:

   • To handle backtracking uniquely, the algorithm appends a negative value of the move when DFS backtracks. This helps in creating a unique path signature for shapes that otherwise may seem similar if traversed differently.

5. Path Conversion and Uniqueness:

   • After a complete island is explored, the path list is converted to a string that represents the full traversal path of the island. This string allows the shape of the island to be expressed uniquely, similar to a sequence of moves in a game.

6. Set Data Structure:

   • A set() is used to store unique island paths. This data structure's inherent property to store only unique items simplifies the task of counting distinct islands. Duplicates are automatically handled.

7. Counts Distinct Islands:

   • The final number of distinct islands is obtained by measuring the length of the set containing the unique path strings.

Here is the code snippet detailing the DFS logic:

1def dfs(i: int, j: int, k: int):
2    grid[i][j] = 0
3    path.append(str(k))
4    dirs = (-1, 0, 1, 0, -1)
5    for h in range(1, 5):
6        x, y = i + dirs[h - 1], j + dirs[h]
7        if 0 <= x < m and 0 <= y < n and grid[x][y]:
8            dfs(x, y, h)
9    path.append(str(-k))

Finally, the number of distinct islands is returned using len(paths) where paths is the set of unique path strings.

By following these stages, the algorithm effectively captures the essence of each island's shape regardless of its location in the grid, allowing us to accurately count the number of distinct islands present.

Example Walkthrough

Let's illustrate the solution approach with a small 4 x 5 grid example:

Assume our grid looks like this, where '1' is land and '0' is water:

11 1 0 0 0
21 1 0 1 1
30 0 0 1 1
40 0 0 0 0

Now, let's walk through the DFS approach outlined above:

1. Start scanning the grid from (0, 0).
2. At (0, 0), find '1' and start DFS, initializing an empty path list.
3. Visit (0, 0), mark as '0', and add direction code to path. Since there's no previous cell, we skip encoding here.
4. From (0, 0), move to (0, 1) (right), mark as '0', and add '2' to path (assuming '2' represents moving right).
5. Continue DFS to (1, 1) (down), mark as '0', and add '3' to path (assuming '3' represents moving down).
6. DFS can't move further, so backtrack appending '-3' to path to return to (0, 1), then append '-2' to backtrack to (0, 0).
7. Since all adjacent '1's are visited, the DFS for this island ends, and the path is ['2', '3', '-3', '-2'].
8. Convert path to a string "233-3-2" and insert into the paths set.
9. Continue scanning the grid and start a new DFS at (1, 3), where the next '1' is found.
10. Repeat the steps to traverse the second island. Assume the resulting path for the second island is "233-3-2".
11. Conversion and insertion into paths set have no effect as it's a duplicate.
12. Finish scanning the grid, with no more '1's left.
13. Count the distinct islands from the paths set, which contains just one unique path string "233-3-2".

We conclude that there is only 1 distinct island in this example grid.

This walkthrough demonstrates how the DFS exploration with unique path encoding can be used to solve this problem, ensuring that only distinct islands are counted even when they are scattered throughout the grid.

Solution Implementation

Time and Space Complexity

The time complexity of the provided code is O(M * N), where M is the number of rows and N is the number of columns in the grid. This is due to the fact that we must visit each cell at least once to determine the islands. The dfs function is called for each land cell (1) and it ensures every connected cell is visited only once by marking visited cells as water (0) immediately, thus avoiding revisiting.

The space complexity is O(M * N) in the worst case. This could happen if the grid is filled with land, and a deep recursive call stack is needed to explore the island. Additionally, the path variable which records the shape of each distinct island can in the worst case take up as much space as all the cells in the grid (if there was one very large island), therefore the space complexity would depend on the input size.

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