Number of distinct islands

Graphs Traversal Problems Medium

Given a boolean 2D matrix grid of size N x M. Find the number of distinct islands where a group of connected 1s (horizontally or vertically) forms an island. Two islands are considered to be distinct if and only if one island is equal to another (not rotated or reflected).

Examples:

Input: grid = [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 1, 1],[0, 0, 0, 1, 1]]

Output: 1

Explanation:

Same colored islands are equal. We have 2 equal islands, so we have only 1 distinct island.

Input: grid = [[1, 1, 0, 1, 1], [1, 0, 0, 0, 0], [0, 0, 0, 0, 1],[1, 1, 0, 1, 1]]

Output: 3

Explanation:

Same colored islands are equal. We have 4 islands, but 2 of them are equal, So we have 3 distinct islands..

Input: grid = [[1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0],[0, 0, 0, 1, 1]]

Constraints

1 <= N, M <= 500
grid[i][j] == 0 or 1

Company Tags

PayPal Cerner Bain & Company MongoDB Flipkart Johnson & Johnson Oracle Alibaba Pinterest Mastercard Instacart NVIDIA Optum Ernst & Young Wayfair DoorDash eBay Splunk Qualcomm Etsy Siemens Healthineers Zoho Square Dropbox Rockstar Games Google Microsoft Amazon Meta Apple Netflix Adobe

Editorial

Intuition:

The goal is to count how many distinct shapes of islands exist in the grid. For that, it must be known how can to distinguish unique islands.

How to identify if two islands are unique or not?

A set data structure is known for storing only unique entries, which can also be used here to store unique islands here.

How to store the islands as an enty in set?

A island can be represented as the path taken to traverse all the land cells in the island. But the problem isn't solved yet. Consider the example:

Here both the islands will be represented as two paths which look identical but consist of different coordinatees and thus will be treated as different entries for the set.

To solve this problem, the relative coordinates of all the cell with respect to a base cell (starting cell) can be stored as path as shown in the illustration:

Approach:

Use a set to store the unique shapes of islands. Use a 2D array to keep track of visited cells. Define directions for moving up, down, left, and right. Create a helper function to check if a cell is within the grid boundaries.
Traverse through the grid. If a cell contains a 1 and hasn't been visited, it indicates the start of a new island.
Use DFS to explore all cells of the island starting from the current cell. Track the relative positions of the cells in the island based on the starting cell. Mark cells as visited during the traversal to avoid revisiting them.
After exploring an island, store its shape (relative positions) in the set. The number of distinct islands is the size of the set containing the unique shapes.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:

    // DelRow and delCol for neighbors
    vector<int> delRow = {-1, 0, 1, 0};
    vector<int> delCol = {0, -1, 0, 1};
  
    /* Helper function to check if a 
    cell is within boundaries */
    bool isValid(int &i, int &j, 
                 int &n, int &m) {
        
        // Return false if cell is invalid
        if(i < 0 || i >= n) return false;
        if(j < 0 || j >= m) return false;
        
        // Return true if cell is valid
        return true;
    }
    
    // Function for DFS traversal of island
    void dfs(int row, int col, 
            vector<vector<int>> &grid, 
            vector<vector<bool>> &visited,
            vector<pair<int,int>> &path,
            int &base_row, int &base_col) {
        
        // Get the dimensions of grid
        int n = grid.size();
        int m = grid[0].size();
        
        /* Add relative position of current 
        cell with respect to the base cell */
        path.push_back({row-base_row, col-base_col});
        
        // Traverse the 4 neighbors
        for(int i=0; i<4; i++) {
            
            // Get coordinates of new cell
            int nRow = row + delRow[i];
            int nCol = col + delCol[i];
            
            // Traverse unvisited, valid, land cell
            if(isValid(nRow, nCol, n, m) &&
               grid[nRow][nCol] == 1 && 
               !visited[nRow][nCol]) {
               
                // Mark the cell as visited
                visited[nRow][nCol] = true;
                
                // Recursively call DFS for the new cell
                dfs(nRow, nCol, grid, visited, path, base_row, base_col);
            }
        }
        
        // Return after all neighbors are explored
        return;
    }
    
public:
    /* Function to count the count of
     distinct islands in the given grid */
    int countDistinctIslands(vector<vector<int>>& grid) {
        
        // Get the dimensions of grid
        int n = grid.size();
        int m = grid[0].size();
        
        // 2-D Visited array
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        
        // Set to store traversal of unique islands
        set <vector <pair <int, int>>> st;
        
        // Traverse the grid
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                
                /* Start BFS traversal if an 
                unvisited land cell is found */
                if(grid[i][j] == 1 && !visited[i][j]) {
                    
                    // Mark the cell as visited
                    visited[i][j] = true;
                    
                    // To store the path of cells
                    vector<pair<int,int>> path;
                    
                    // Start DFS traversal from the cell
                    dfs(i, j, grid, visited, path, i, j);
                    
                    // Add the path of explored island to the set
                    st.insert(path);
                }
            }
        }
        
        return st.size();
    }
};

int main() {
    vector<vector<int>> grid = {
        {1, 1, 0, 1, 1}, 
        {1, 0, 0, 0, 0},
        {0, 0, 0, 0, 1},
        {1, 1, 0, 1, 1}
	};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function to count the count of
     distinct islands in the given grid */
    int ans = sol.countDistinctIslands(grid);
    
    // Output
    cout << "The count of distinct islands in the given grid is: " << ans << endl;
    
    
    return 0;
}
import java.util.*;

class Solution {
    // DelRow and delCol for neighbors
    private int[] delRow = {-1, 0, 1, 0};
    private int[] delCol = {0, -1, 0, 1};

    /* Helper function to check if a 
    cell is within boundaries */
    private boolean isValid(int i, int j, int n, int m) {
        // Return false if cell is invalid
        if (i < 0 || i >= n) return false;
        if (j < 0 || j >= m) return false;
        // Return true if cell is valid
        return true;
    }

    // Function for DFS traversal of island
    private void dfs(int row, int col, int[][] grid, boolean[][] visited,
                     List<String> path, int baseRow, int baseCol) {
        // Get the dimensions of grid
        int n = grid.length;
        int m = grid[0].length;

        /* Add relative position "row,col" of current 
        cell with respect to the base cell */
        path.add((row - baseRow) + "," + (col - baseCol));

        // Traverse the 4 neighbors
        for (int i = 0; i < 4; i++) {
            // Get coordinates of new cell
            int nRow = row + delRow[i];
            int nCol = col + delCol[i];

            // Traverse unvisited, valid, land cell
            if (isValid(nRow, nCol, n, m) && grid[nRow][nCol] == 1 && !visited[nRow][nCol]) {
                // Mark the cell as visited
                visited[nRow][nCol] = true;

                // Recursively call DFS for the new cell
                dfs(nRow, nCol, grid, visited, path, baseRow, baseCol);
            }
        }
    }

    /* Function to count the number of
    distinct islands in the given grid */
    public int countDistinctIslands(int[][] grid) {
        // Get the dimensions of grid
        int n = grid.length;
        int m = grid[0].length;

        // 2-D Visited array
        boolean[][] visited = new boolean[n][m];

        // Set to store traversal of unique islands
        Set<List<String>> st = new HashSet<>();

        // Traverse the grid
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                /* Start DFS traversal if an 
                unvisited land cell is found */
                if (grid[i][j] == 1 && !visited[i][j]) {
                    // Mark the cell as visited
                    visited[i][j] = true;

                    // To store the path of cells
                    List<String> path = new ArrayList<>();

                    // Start DFS traversal from the cell
                    dfs(i, j, grid, visited, path, i, j);

                    // Add the path of explored island to the set
                    st.add(path);
                }
            }
        }

        return st.size();
    }
}

class Main {
    public static void main(String[] args) {
        int[][] grid = {
            {1, 1, 0, 1, 1},
            {1, 0, 0, 0, 0},
            {0, 0, 0, 0, 1},
            {1, 1, 0, 1, 1}
        };

        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();

        /* Function to count the number of
        distinct islands in the given grid */
        int ans = sol.countDistinctIslands(grid);

        // Output
        System.out.println("The count of distinct islands in the given grid is: " + ans);
    }
}
from typing import List

class Solution:
    # DelRow and delCol for neighbors
    delRow = [-1, 0, 1, 0]
    delCol = [0, -1, 0, 1]
  
    # Helper function to check if a 
    # cell is within boundaries
    def isValid(self, i, j, n, m):
        # Return false if cell is invalid
        if i < 0 or i >= n: return False
        if j < 0 or j >= m: return False
        # Return true if cell is valid
        return True
    
    # Function for DFS traversal of island
    def dfs(self, row, col, grid, visited, 
            path, base_row, base_col):
        # Get the dimensions of grid
        n = len(grid)
        m = len(grid[0])
        
        # add relative position of current 
        # cell with respect to the base cell
        path.append((row-base_row, col-base_col))
        
        # Traverse the 4 neighbors
        for i in range(4):
            # Get coordinates of new cell
            nRow = row + self.delRow[i]
            nCol = col + self.delCol[i]
            
            # Traverse unvisited, valid, land cell
            if (self.isValid(nRow, nCol, n, m) and 
                grid[nRow][nCol] == 1 and 
                not visited[nRow][nCol]):
                    
                # Mark the cell as visited
                visited[nRow][nCol] = True
                
                # Recursively call DFS for the new cell
                self.dfs(nRow, nCol, grid, visited, 
                         path, base_row, base_col)
        
        # Return after all neighbors are explored
        return
    
    # Function to count the count of
    # distinct islands in the given grid
    def countDistinctIslands(self, grid: List[List[int]]) -> int:
        
        # Get the dimensions of grid
        n = len(grid)
        m = len(grid[0])
        
        # 2-D Visited array
        visited = [[False for _ in range(m)] for _ in range(n)]
        
        # Set to store traversal of unique islands
        st = set()
        
        # Traverse the grid
        for i in range(n):
            for j in range(m):
                
                # Start BFS traversal if an 
                # unvisited land cell is found
                if grid[i][j] == 1 and not visited[i][j]:
                    
                    # Mark the cell as visited
                    visited[i][j] = True
                    
                    # To store the path of cells
                    path = []
                    
                    # Start DFS traversal from the cell
                    self.dfs(i, j, grid, visited, path, i, j)
                    
                    # Add the path of explored island to the set
                    st.add(tuple(path))
        
        return len(st)

# Example usage
grid = [
    [1, 1, 0, 1, 1], 
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1],
    [1, 1, 0, 1, 1]
]

# Creating an instance of Solution class
sol = Solution()

# Function to count the count of distinct islands in the given grid
ans = sol.countDistinctIslands(grid)

# Output
print("The count of distinct islands in the given grid is:", ans)
class Solution {
    constructor() {
        // DelRow and delCol for neighbors
        this.delRow = [-1, 0, 1, 0];
        this.delCol = [0, -1, 0, 1];
    }
  
    /* Helper function to check if a 
    cell is within boundaries */
    isValid(i, j, n, m) {
        // Return false if cell is invalid
        if (i < 0 || i >= n) return false;
        if (j < 0 || j >= m) return false;
        // Return true if cell is valid
        return true;
    }
    
    // Function for DFS traversal of island
    dfs(row, col, grid, visited, path, base_row, base_col) {
        // Get the dimensions of grid
        const n = grid.length;
        const m = grid[0].length;
        
        // add relative position of current 
        // cell with respect to the base cell
        path.push([row - base_row, col - base_col]);
        
        // Traverse the 4 neighbors
        for (let i = 0; i < 4; i++) {
            // Get coordinates of new cell
            const nRow = row + this.delRow[i];
            const nCol = col + this.delCol[i];
            
            // Traverse unvisited, valid, land cell
            if (this.isValid(nRow, nCol, n, m) && grid[nRow][nCol] === 1 && !visited[nRow][nCol]) {
                // Mark the cell as visited
                visited[nRow][nCol] = true;
                // Recursively call DFS for the new cell
                this.dfs(nRow, nCol, grid, visited, path, base_row, base_col);
            }
        }
        
        // Return after all neighbors are explored
        return;
    }
    
    /* Function to count the count of
    distinct islands in the given grid */
    countDistinctIslands(grid) {
        // Get the dimensions of grid
        const n = grid.length;
        const m = grid[0].length;
        
        // 2-D Visited array
        const visited = Array.from({ length: n }, () => Array(m).fill(false));
        
        // Set to store traversal of unique islands
        const st = new Set();
        
        // Traverse the grid
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                // Start BFS traversal if an 
                // unvisited land cell is found
                if (grid[i][j] === 1 && !visited[i][j]) {
                    // Mark the cell as visited
                    visited[i][j] = true;
                    // To store the path of cells
                    const path = [];
                    // Start DFS traversal from the cell
                    this.dfs(i, j, grid, visited, path, i, j);
                    // Add the path of explored island to the set
                    st.add(JSON.stringify(path));
                }
            }
        }
        
        return st.size;
    }
}

// Example usage
const grid = [
    [1, 1, 0, 1, 1], 
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1],
    [1, 1, 0, 1, 1]
];

// Creating an instance of Solution class
const sol = new Solution();

// Function to count the count of distinct islands in the given grid
const ans = sol.countDistinctIslands(grid);

// Output
console.log("The count of distinct islands in the given grid is:", ans);

Complexity Analysis:

Time Complexity: O(N*M*log(N*M)) (where N and M are dimensions of grid)

In the worst case, the DFS call will be made for N*M cells taking O(N*M) time.
In worst case, the set will store O(N*M) entries that takes O(N*M*log(N*M)) time.

Space Complexity: O(N*M)
The visited array takes O(N*M) space and the set will store a maximum of O(N*M) cells.

Code

Problem List