Vultr DocsLatest Content

Number of Distinct Islands

Updated on 07 July, 2025
Number of Distinct Islands header image

Problem Statement

In this problem, you are provided with an m x n binary matrix called grid, which represents a map where 1 indicates land and 0 indicates water. An island is a contiguous group of 1s connected either horizontally or vertically but not diagonally. The task is to identify distinct islands in this grid. Distinct islands are islands that have the same shape and can be translated (shifted in any direction without rotation or reflection) to match exactly with another island. The challenge is to find the total number of such distinct islands present in the matrix.

Examples

Example 1

Input:

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

Output:

1

Example 2

Input:

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

Output:

3

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] is either 0 or 1.

Approach and Intuition

To solve this problem, we have to systematically explore each element of the grid, and when we find a land cell (1), we should perform a depth-first search (DFS) or breadth-first search (BFS) to track the entire island structure. Here's an outlined approach:

  1. Initialize visitation tracking, typically using a set or matrix to keep track of which cells have been visited.
  2. Traverse the matrix cell by cell. When you encounter an unvisited 1, you initiate a DFS or BFS from that cell.
  3. For tracking whether two islands are the same, besides marking the visited cells, use a pattern or a path signature strategy. For example, as you perform DFS, you can record the direction moves (up, down, left, right represented perhaps as 'U', 'D', 'L', 'R') relative to the starting cell of the traversal. This string can serve as a unique identifier for the shape and structure of an island.
  4. Store each unique island signature in a set — since sets automatically handle duplicates, any repeated island shape will not be added again.
  5. The final count of distinct islands will be the size of this set of unique island signatures.

Key challenges and considerations include:

  • Boundary conditions need careful handling to ensure searches do not go out of the grid limits.
  • Efficiently differentiating between island shapes and efficiently storing and comparing these shapes.
  • Ensuring complete visitation of each potential island part once an island cell is found.

Examples from the prompt:

  • In Example 1, the grid forms one island that repeats itself. Thus, despite the island appearing twice, the answer is 1.
  • In Example 2, different configurations and disconnected parts mean there are a total of 3 distinct islands.

The constraints (1 <= m, n <= 50) allow for a full exploration of the grid without the need for exceptionally complex optimizations.

Solutions

  • Java
java 
class IslandCounter {
    private int[][] matrix;
    private boolean[][] checked;
    private StringBuilder islandShape;
    
    public int countUniqueIslands(int[][] matrix) {  
        this.matrix = matrix;
        this.checked = new boolean[matrix.length][matrix[0].length];
        Set<String> uniqueIslands = new HashSet<>();
        for (int x = 0; x < matrix.length; x++) {
            for (int y = 0; y < matrix[0].length; y++) {
                islandShape = new StringBuilder();
                explore(x, y, '0');
                if (islandShape.length() == 0) {
                    continue;
                }
                uniqueIslands.add(islandShape.toString());
            }
        }
        return uniqueIslands.size();
    }
       
    private void explore(int x, int y, char direction) {
        if (x < 0 || y < 0 || x >= matrix.length || y >= matrix[0].length) {
            return;
        }
        if (checked[x][y] || matrix[x][y] == 0) {
            return;
        }
        checked[x][y] = true;
        islandShape.append(direction);
        explore(x + 1, y, 'D');
        explore(x - 1, y, 'U');
        explore(x, y + 1, 'R');
        explore(x, y - 1, 'L');
        islandShape.append('0');
    }
}

The solution provided tackles the problem of determining the number of distinct islands in a 2D grid. Each island is made up of connected land cells (represented by 1s) separated by water cells (represented by 0s). The distinction of each island is based on its shape rather than just the count of cells.

Here is an outline that summarizes the approach implemented in your Java code:

  • Initialize a class IslandCounter with a private 2D integer array matrix for the grid and a 2D boolean array checked to keep track of the cells that have already been visited.
  • Declare a StringBuilder islandShape to dynamically record the shape of the island during exploration.
  • Implement the countUniqueIslands function which:
    • Takes a 2D integer array matrix.
    • Initializes the checked array to ensure all cells are initially set as not visited.
    • Uses a HashSet uniqueIslands to store unique island shapes – uniqueness determined by their navigation path string created during the exploration.
    • Iterates through each cell in the matrix, using the helper function explore to navigate through the island from each unvisited land cell, concatenating directions to the islandShape to form a unique identifier for the shape of the island.
    • Adds the completed island shape to the set of unique islands if not seen before.
    • Returns the size of uniqueIslands set, which corresponds to the number of distinct islands.
  • The explore function:
    • Is a recursive function that receives coordinates (x, y) and the direction from which it was called.
    • Base case checks ensure it does not explore out of bounds or revisit cells or traverse water cells.
    • Marks the cell as visited and updates the islandShape with the direction moved.
    • Recursively calls itself for the four possible directions (up, down, left, right).
    • Upon returning from each recursive call, appends a termination mark to signal the end of that path sequence, aiding in distinguishing between different structures.

Implement this solution effectively ensures that each distinct shape of the island is recognized, counting only truly unique islands. The inclusion of navigation paths in the shape definition is key to distinguishing between islands of similar sizes but different configurations.

  • Python
python 
class Solution:
    def countUniqueIslands(self, matrix: List[List[int]]) -> int:
        def exploreIsland(x, y, dir):
            if x < 0 or y < 0 or x >= len(matrix) or y >= len(matrix[0]):
                return
            if (x, y) in visited or matrix[x][y] == 0:
                return
            visited.add((x, y))
            island_pattern.append(dir)
            exploreIsland(x + 1, y, "D")
            exploreIsland(x - 1, y, "U")
            exploreIsland(x, y + 1, "R")
            exploreIsland(x, y - 1, "L")
            island_pattern.append("back")
            
        visited = set()
        distinct_islands = set()
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                island_pattern = []
                exploreIsland(i, j, "start")
                if island_pattern:
                    distinct_islands.add(tuple(island_pattern))
            
        return len(distinct_islands)

The provided code defines a solution for determining the number of distinct islands in a given 2D matrix where islands are represented with 1s and water with 0s.

Ensure the matrix is passed to the countUniqueIslands function. The function employs a nested helper function named exploreIsland, which uses a depth-first search (DFS) approach to traverse the island and capture its unique shape. This is accomplished using directions as markers during the traversal, allowing for a distinctive pattern representation of each island.

  • The algorithm starts by initializing a visited set to keep track of visited grid cells and a distinct_islands set to store unique patterns of islands.
  • Iteration through the matrix cells occurs, and for each unvisited cell marked by a 1, exploreIsland is invoked.
  • The exploreIsland performs DFS from the current cell in all four cardinal directions (Down, Up, Right, Left), appending the move direction to the island_pattern list and marking the position as visited.
  • Upon retracing steps in the DFS ('backtracking'), the word "back" is added to the pattern.
  • Once an island pattern traversal is completed, its tuple representation (to ensure immutability and hashability) is added to distinct_islands if it's not already present.
  • The main function returns the count of distinct island patterns found by converting the length of the distinct_islands set to an integer.

In summary, the function uniquely identifies islands based on their shape and relative cell positions within the matrix, disregarding identical islands' different locations. This Python solution is efficient, leveraging set operations for quick look-ups and ensuring no redundant pattern storage through unique tuple checks.

Comments

No comments yet.