> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/number-of-distinct-islands.md).

# Number of Distinct Islands

Given a non-empty 2D array `grid` of 0's and 1's, an **island** is a group of `1`'s (representing land) connected 4-directionally (horizontal or vertical). You may assume all four edges of the grid are surrounded by water.

Count the number of **distinct** islands. An island is considered to be the same as another if and only if one island has the same shape as another island (and not rotated or reflected).

Notice that:

```
11
1
```

and

```
 1
11
```

are considered different island, because we do not consider reflection / rotation.

The length of each dimension in the given `grid` does not exceed `50`.

#### Example

**Example 1:**

```
Input: 
  [
    [1,1,0,0,1],
    [1,0,0,0,0],
    [1,1,0,0,1],
    [0,1,0,1,1]
  ]
Output: 3
Explanation:
  11   1    1
  1        11   
  11
   1
```

**Example 2:**

```
Input:
  [
    [1,1,0,0,0],
    [1,1,0,0,0],
    [0,0,0,1,1],
    [0,0,0,1,1]
  ]
Output: 1
```

```java
public class Solution {
    int[][] dir = { { 1, 0 }, { 0, 1 }, { 0, -1 }, { -1, 0 } };

    public void DFS(int[][] grid, boolean[][] visited, int x0, int y0, int x, int y, StringBuilder str) {
        visited[x][y] = true;
        int relX = x - x0, relY = y - y0;
        str.append("(" + relX + " " + relY + ")");
        for (int i = 0; i < 4; i++) {
            int newX = x + dir[i][0], newY = y + dir[i][1];
            if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[0].length && grid[newX][newY] == 1
                    && !visited[newX][newY])
                DFS(grid, visited, x0, y0, newX, newY, str);
        }
    }

    public int numberofDistinctIslands(int[][] grid) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        Set<String> set = new HashSet<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    StringBuilder island = new StringBuilder();
                    DFS(grid, visited, i, j, i, j, island);
                    set.add(island.toString());
                }
            }
        }
        return set.size();
    }
}
```