Distinct Islands

Problem Link - Distinct Islands

You are given a two-dimensional array/list of integers consisting of 0s and 1s. In the list, 1 represents land and 0 represents water.

The task is to find the number of distinct islands where a group of connected 1s(horizontally or vertically) forms an island.

Note:
Two islands are considered to be the same if and only if one island is equal to another(not rotated or reflected) i.e if we can translate one island on another without rotating or reflecting then it would be considered as the same islands.

Example - 1

Input -
1 1 0
0 0 1
0 0 1
Output - 2 islands

Example - 2

1 1 0 0 0
1 1 0 0 0
0 0 0 1 1
0 0 0 1 1
In this example, we have two islands and they are the same as we can translate one island onto another island, so our answer should be 1.

To solve this, We can convert this problem into a graph problem.
Let's see how it can be done.

Intuition
We can think this grid as graph where each cell that contains 1 acts a node in graph, and each cell has upto 4 neighbouring nodes(left,right,top,bottom) and there is edge between 2 nodes of 1 if they are adjacent(either horizontally or vertically) and treat remaining cell that contains zeroes as nothing.

So after forming this problem into a graph problem, our goal finding total number of islands is converted into as finding total number of components in the graph. Here components refers to islands.

In graph theory, a connected component is a group of nodes where every pair of nodes is reachable from one another. Similarly, in this grid, an island is a connected component of land ('1') cells. Each '1' can be thought of as a node, and edges exist between neighboring land cells (adjacent '1's)."

To find all components, we will do a traversal(dfs or bfs) from any unvisited '1' cell to all of its connected neighbours.

Approach

• We will start iterating through the grid, where each grid cell is treated as node.
• when you encounter a unvisited '1' node,this means you've found one island,so call the dfs to find all its connected components.
• DFS Traversal: From the current '1', explore all its neighboring '1's in the four cardinal directions (up, down, left, right), similar to exploring nodes in a graph using DFS.
• Mark all visited cells as part of the current component (e.g., flip them to '0' or store them in a visited set).
• after traversal, increment the count the number of islands.

How to store distinct islands or count the distinct islands?

for this we will store the shape of the islands that we found.

Next question is How to store this shape of the islands found?

So what happens, if we store the co-ordinates of the islands in a vector list ?

this doesn't work. we need to find a way on how to store the co-ordinates of identical islands.

*for that, We can call one of the starting points a base, and subtract the base coordinates from the land’s coordinates (Cell Coordinates - Base coordinates). *

Code

void dfs(int i, int j, int n, int m,
 int base_i, int base_j, int** arr, vector<pair<int, int>>& island) {
    // Boundary check and visit check
    if (i < 0 || j < 0 || i >= n || j >= m || arr[i][j] == 0)
        return;

    // Mark the current cell as visited
    arr[i][j] = 0;

    // Add the relative position of the current cell to the base cell
    island.push_back({i - base_i, j - base_j});

    // Directions for up, right, down, left
    int di[4] = {-1, 0, 1, 0};
    int dj[4] = {0, 1, 0, -1};

    // Explore all 4 neighbors
    for (int k = 0; k < 4; k++) {
        int new_i = i + di[k];
        int new_j = j + dj[k];
        dfs(new_i, new_j, n, m, base_i, base_j, arr, island);
    }
}


int distinctIslands(int** arr, int n, int m) {
    int count = 0;
    set<vector<pair<int, int>>> st;

    // Iterate through each cell of the grid
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 1) {
                vector<pair<int, int>> vec;
                dfs(i, j, n, m, i, j, arr, vec);  // Perform DFS
                st.insert(vec);  // Insert the vector representing the island shape
            }
        }
    }

    // The size of the set is the number of distinct islands
    return st.size();
}

Time Complexity: O(N x M x log(N x M)) + O(NxMx4) ~ O(N x M), For the worst case, assuming all the pieces as land, the DFS function will be called for (N x M) nodes, and for every node, we are traversing for 4 neighbors, it will take O(N x M x 4) time. Set at max will store the complete grid, so it takes log(N x M) time.

Space Complexity ~ O(N x M), O(N x M) for the visited array and set takes up N x M locations at max.