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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

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

1class Solution:
2    def numDistinctIslands(self, grid: List[List[int]]) -> int:
3        # Depth-first search function to explore the island
4        def depth_first_search(i: int, j: int, move: int):
5            grid[i][j] = 0  # Marking the visited cell as '0' to avoid revisiting
6            path.append(str(move))  # Add the move direction to path
7            # Possible movements in the four directions: up, right, down, left
8            directions = (-1, 0, 1, 0, -1)
9            # Iterating over the four possible directions
10            for h in range(4):
11                # Calculate new cell's coordinates
12                x, y = i + directions[h], j + directions[h+1]
13                # Check if the new cell is within bounds and is part of an island
14                if 0 <= x < m and 0 <= y < n and grid[x][y]:
15                    depth_first_search(x, y, h+1)
16            path.append(str(-move))  # Add the reverse move to path to differentiate shapes
17
18        # Set to store unique paths that represent unique island shapes
19        paths = set()
20        # Temporary list to store the current island's path shape
21        path = []
22        # Dimensions of the grid
23        m, n = len(grid), len(grid[0])
24
25        # Iterate over every cell in the grid
26        for i, row in enumerate(grid):
27            for j, value in enumerate(row):
28                if value:  # Check if the cell is part of an island
29                    depth_first_search(i, j, 0)  # Start DFS from this cell
30                    paths.add("".join(path))  # Add the path shape to the set of paths
31                    path.clear()  # Clear the path for next island
32
33        # Number of distinct islands is the number of unique path shapes
34        return len(paths)
35
1class Solution {
2    private int rows; // number of rows in the grid
3    private int cols; // number of columns in the grid
4    private int[][] grid; // grid representation
5    private StringBuilder path; // used to store the path during DFS to identify unique islands
6
7    public int numDistinctIslands(int[][] grid) {
8        rows = grid.length; // set the number of rows
9        cols = grid[0].length; // set the number of columns
10        this.grid = grid; // reference the grid
11        Set<String> uniqueIslands = new HashSet<>(); // store unique island paths as strings
12        for (int i = 0; i < rows; ++i) {
13            for (int j = 0; j < cols; ++j) {
14                if (grid[i][j] == 1) { // if it's part of an island
15                    path = new StringBuilder(); // initialize the path
16                    exploreIsland(i, j, 'S'); // start DFS with dummy direction 'S' (Start)
17                    uniqueIslands.add(path.toString()); // add the path to the set
18                }
19            }
20        }
21        return uniqueIslands.size(); // the number of unique islands
22    }
23
24    private void exploreIsland(int i, int j, char direction) {
25        grid[i][j] = 0; // mark as visited
26        path.append(direction); // append the direction to path
27      
28        // directions represented as delta x and delta y
29        int[] dX = {-1, 0, 1, 0};
30        int[] dY = {0, 1, 0, -1};
31        char[] dirCodes = {'U', 'R', 'D', 'L'}; // corresponding directional codes
32      
33        for (int dir = 0; dir < 4; ++dir) { // iterate over possible directions
34            int x = i + dX[dir];
35            int y = j + dY[dir];
36            if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 1) { // check for valid next cell
37                exploreIsland(x, y, dirCodes[dir]); // recursive DFS call
38            }
39        }
40      
41        path.append('B'); // append backtrack code to ensure paths are unique after recursion return
42    }
43}
44
1#include <vector>
2#include <string>
3#include <unordered_set>
4#include <functional> // Include necessary headers
5
6class Solution {
7public:
8    int numDistinctIslands(vector<vector<int>>& grid) {
9        unordered_set<string> uniqueIslandPaths; // Store unique representations of islands
10        string currentPath; // Store the current traversal path
11        int rowCount = grid.size(), colCount = grid[0].size(); // Dimensions of the grid
12        int directions[5] = {-1, 0, 1, 0, -1}; // Used for moving in the grid
13
14        // Depth-first search (DFS) to traverse islands and record paths
15        function<void(int, int, int)> dfs = [&](int row, int col, int moveDirection) {
16            grid[row][col] = 0; // Mark the current cell as visited
17            currentPath += to_string(moveDirection); // Record move direction
18
19            // Explore all possible directions: up, right, down, left
20            for (int d = 1; d < 5; ++d) {
21                int newRow = row + directions[d - 1], newCol = col + directions[d];
22                if (newRow >= 0 && newRow < rowCount && newCol >= 0 && newCol < colCount && grid[newRow][newCol]) {
23                    // Continue DFS if the next cell is part of the island (i.e., grid value is 1)
24                    dfs(newRow, newCol, d);
25                }
26            }
27
28            // Record move direction again to differentiate between paths with same shape but different sizes
29            currentPath += to_string(moveDirection);
30        };
31
32        // Iterate over all grid cells to find all islands
33        for (int i = 0; i < rowCount; ++i) {
34            for (int j = 0; j < colCount; ++j) {
35                // If the cell is part of an island
36                if (grid[i][j]) {
37                    dfs(i, j, 0); // Start DFS
38                    uniqueIslandPaths.insert(currentPath); // Add the path to the set
39                    currentPath.clear(); // Reset path for the next island
40                }
41            }
42        }
43
44        // The number of unique islands is the size of the set containing unique paths
45        return uniqueIslandPaths.size();
46    }
47};
48
1function numDistinctIslands(grid: number[][]): number {
2    const rowCount = grid.length; // The number of rows in the grid.
3    const colCount = grid[0].length; // The number of columns in the grid.
4    const uniquePaths: Set<string> = new Set(); // Set to store unique island shapes.
5    const currentPath: number[] = []; // Array to keep the current DFS path.
6    const directions: number[] = [-1, 0, 1, 0, -1]; // Array for row and column movements.
7
8    // Helper function to perform DFS.
9    const dfs = (row: number, col: number, directionIndex: number) => {
10        grid[row][col] = 0; // Mark the cell as visited by setting it to 0.
11        currentPath.push(directionIndex); // Append the direction index to the current path.
12
13        // Explore all four directions: up, right, down, left.
14        for (let i = 1; i < 5; ++i) {
15            const nextRow = row + directions[i - 1];
16            const nextCol = col + directions[i];
17
18            // Check if the next cell is within bounds and not visited.
19            if (nextRow >= 0 && nextRow < rowCount && nextCol >= 0 && nextCol < colCount && grid[nextRow][nextCol]) {
20                dfs(nextRow, nextCol, i); // Recursively perform DFS on the next cell.
21            }
22        }
23
24        // Upon return, push the backtracking direction index to the current path.
25        currentPath.push(directionIndex);
26    };
27
28    // Iterate through all cells of the grid.
29    for (let row = 0; row < rowCount; ++row) {
30        for (let col = 0; col < colCount; ++col) {
31            // If the current cell is part of an island (value is 1).
32            if (grid[row][col]) {
33                dfs(row, col, 0); // Start DFS from the current cell.
34                uniquePaths.add(currentPath.join(',')); // Add the current path to the set of unique paths.
35                currentPath.length = 0; // Reset the currentPath for the next island.
36            }
37        }
38    }
39
40    return uniquePaths.size; // Return the number of distinct islands.
41}
42

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.


Fast Track Your Learning with Our Quick Skills Quiz:

What data structure does Breadth-first search typically uses to store intermediate states?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄