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

# Number of Distinct Islands

## Problem

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 can be translated (and not rotated or reflected) to equal the other.

![](/files/-MQ_5Lo2x4YaBP_rTqu5)

![](/files/-MQ_5QPX094l5N73AIEq)

### Thought Process

* Since we are dealing with a distinct characteristic, we can utilize a hash set

![](/files/-MQ_FvWpTiMFhXjOKg6H)

## Solution

```
class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        
        islandSet = set()
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:  
                    self.path = "" #needs to be global variable 
                    self.dfsearch(i,j,grid,"s")
                    print(self.path)
                    islandSet.add(self.path)
                    
        print(islandSet)
        return len(islandSet)
                
    def dfsearch(self, i, j, grid, direction):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != 1:
            return 
        
        grid[i][j] = 0
        self.path+=direction
        
        self.dfsearch(i-1,j,grid,"u")
        self.dfsearch(i+1,j,grid,"d")
        self.dfsearch(i,j-1,grid,"l")
        self.dfsearch(i,j+1,grid,"r")
        
        self.path+="e"
        
```

## Time Complexity

* **Time:** O(m\*n)
* **Space:** O(m\*n)