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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://joshualbarb.gitbook.io/leetcode-problems/graphs/number-of-distinct-islands.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.