Number Of Distinct Islands - Leetcode Solution

The problem "Number of Distinct Islands" on LeetCode asks us to find the number of distinct islands in a 2D grid. An island is defined as a group of connected 1's (representing land) and is considered distinct if no other island has the same shape, orientation, and size.

To solve this problem, we can use the concept of graph traversal. We can traverse the entire grid and look for an island (a group of connected 1's). Once we find an island, we can mark all the cells of that island as visited and then store its shape, orientation, and size in a set. We can then continue traversing the grid and look for the next unvisited island.

Let's break down the steps of our algorithm:

1. Define a set to store the shapes of distinct islands. Initialize it to an empty set. Also, define a 2D boolean array to keep track of visited cells. Initialize all the cells to False.

2. Traverse the entire 2D grid using nested for-loops. At each cell (i,j), do the following- a. If the cell is not visited and contains a 1, it means we have found an unvisited island. So, we call the dfs function to explore this island. b. The dfs function takes in current cell indices and a string variable to store the shape of the island. c. In the dfs function, if the current cell is out of bounds or has already been visited or contains a 0, we return immediately. d. Otherwise, we mark the current cell as visited and add the relative index (position of the current cell with respect to the starting cell) to the shape string. e. Then, for each of the four neighbors of the current cell, we call the dfs function recursively with the neighbor cell's indices. f. After we have explored all the cells of the island, we add the shape string to the set of distinct islands. g. Return from dfs function.

3. After we have traversed the entire grid, the size of the distinct island set is the answer to our problem.

Here's the Python code for the solution described above:

class Solution:

    def dfs(self, grid, i, j, shape):
        if i<0 or i>=len(grid) or j<0 or j>=len(grid[0]) or grid[i][j]==0 or self.visited[i][j]:
            return
        
        self.visited[i][j] = True
        shape.append((i-self.row, j-self.col))
        
        self.dfs(grid, i+1, j, shape)
        self.dfs(grid, i-1, j, shape)
        self.dfs(grid, i, j+1, shape)
        self.dfs(grid, i, j-1, shape)
        
        
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        self.visited = [[False for j in range(len(grid[0]))] for i in range(len(grid))]
        self.distinctIslands = set()
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if not self.visited[i][j] and grid[i][j]==1:
                    self.row, self.col = i, j
                    shape = []
                    self.dfs(grid, i, j, shape)
                    self.distinctIslands.add(tuple(shape))
                    
        
        return len(self.distinctIslands)

The time complexity of this solution is O(mn), where m is the number of rows and n is the number of columns of the grid. This is because we traverse the entire grid once and perform DFS search on each unvisited island. The space complexity is also O(mn) because we use a 2D boolean array to keep track of visited cells and a set to store distinct island shapes.

1