> 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

DFS

## 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.

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MQZJCPMKjpBLJB7mHdw%2F-MQ_5Lo2x4YaBP_rTqu5%2FScreen%20Shot%202021-01-08%20at%208.03.31%20PM.png?alt=media\&token=00a4aa0e-8d5f-4d11-97de-178bbe1e2ebf)

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MQZJCPMKjpBLJB7mHdw%2F-MQ_5QPX094l5N73AIEq%2FScreen%20Shot%202021-01-08%20at%208.03.52%20PM.png?alt=media\&token=2aafaf25-d638-470e-a5eb-37a0ad3b5a75)

### Thought Process

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

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MQZJCPMKjpBLJB7mHdw%2F-MQ_FvWpTiMFhXjOKg6H%2FIMG_1C26DA9439BD-1.jpeg?alt=media\&token=52021a6e-05f8-4262-af8f-a08763368df6)

## 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)