Problem Statement

Given a 2D grid grid[][] of n rows and m columns where:

• grid[i][j] == 1 represents land.
• grid[i][j] == 0 represents water.

An island is a group of connected 1s (land) connected in one of the four directions (left, right, up, down). Two islands are considered distinct if one island cannot be transformed into the other simply by shifting (translating). Your task is to determine the number of distinct islands in the grid.

Input:

• grid[][]: A 2D matrix with values 1 and 0.
• n: Number of rows in the grid.
• m: Number of columns in the grid.

Output:

• An integer representing the number of distinct islands.

Examples

Example 1:

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

Explanation:
The first island has the relative coordinates [(0, 0), (0, 1), (1, 0)].
The second island also has the relative coordinates [(0, 0), (0, 1), (1, 0)].
Since both islands have the same shape (relative positions), they are not distinct.

Example 2:

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

Explanation:
First island at (0, 0) consists of the cells: [(0, 0), (0, 1), (1, 0)].
Second island at (2, 2) consists of the cells: [(2, 2), (2, 3), (3, 2), (3, 3)].
The shapes of these islands are distinct:

First island: shape [(0, 0), (0, 1), (1, 0)].
Second island: shape [(0, 0), (0, 1), (1, 0), (1, 1)].
Thus, there are 2 distinct islands.

Example 3:

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

Output: 1

Explanation:
One island at (0, 0) consists of all connected cells: [(0, 0), (0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), (2, 2)].
Since there is only one island, the number of distinct islands is 1.

Different Approaches

1️⃣ Breadth-First Approach (BFS)

Intuition:
The objective is to count how many distinct shapes of islands exist in the grid. To achieve this, we need a way to determine whether two islands are the same or different. This raises the question of how to identify unique islands.

How do we distinguish between two islands?
The idea is to use a data structure that stores only unique entries, and a set is perfect for this task. We can store each island’s shape as an entry in the set, and the number of distinct entries will give us the number of distinct islands.

How to represent an island in the set?
One way to represent an island is by recording the path taken while traversing through all the connected land cells (1s) of that island. This will capture the relative positions of the land cells with respect to the starting point. The resulting path can be used as a unique identifier for the shape of the island.

Approach:

1. 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.
2. Traverse through the grid. If a cell contains a 1 and hasn't been visited, it indicates the start of a new island.
3. 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.
4. 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.

Code:

#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;
}

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.