Number Of Distinct Islands Ii - Leetcode Solution

Problem Description:

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.

Example:

Input: [ [1,1,0,0,1], [1,0,0,0,0], [1,1,0,0,1], [0,1,0,1,1] ] Output: 3 Explanation: The figure corresponding to the upper-left corner is the same as the one corresponding to the bottom-right corner.

Solution:

The problem can be solved using DFS and hashing. Islands are considered different if they are translated and not rotated or reflected. So, for each distinct island, we can hash it based on the shape and relative position of its cells.

First, we define our hashing function. Since we cannot rotate or reflect islands, we can give each neighboring cell a unique number in the range [1,8]. We then sort these numbers in ascending order and concatenate them to form a string, which we can use as the hash key. We also store the starting position of the island as a tuple (i,j).

def get_hash_key(grid, i, j): m, n = len(grid), len(grid[0]) dirs = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(-1,-1),(1,-1),(-1,1)] cells = [] for dir in dirs: x, y = i + dir[0], j + dir[1] if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == 0: cells.append(0) else: cells.append(grid[x][y]) cells.sort() return str(cells)

Next, we define our recursive DFS function to explore each connected component and hash it. For each cell in the component, we mark it as visited and add its hash key to a set. We also maintain a list of relative positions of the visited cells in the component as tuples (x,y).

def explore_component(grid, i, j, positions): m, n = len(grid), len(grid[0]) if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0: return grid[i][j] = 0 positions.append((i,j)) for dir in [(0,1),(0,-1),(1,0),(-1,0)]: explore_component(grid, i+dir[0], j+dir[1], positions) for k in range(4,8): x, y = positions[k] if grid[x][y] == 1: rel_pos = [(x-i,y-j) for (x,y) in positions] rel_pos.sort() shape_key = get_hash_key(rel_pos) islands.add((shape_key, (i,j)))

Finally, we traverse the entire grid using the DFS function and add each distinct island to a set. We return the size of the set as the number of distinct islands.

def numDistinctIslands2(grid): global islands islands = set() m, n = len(grid), len(grid[0]) for i in range(m): for j in range(n): if grid[i][j] == 1: positions = [] explore_component(grid, i, j, positions) return len(islands)

Overall, the time complexity of the algorithm is O(mnlog(mn)) due to the sorting involved in the hashing function. The space complexity is also O(mn) for the visited set.

1