unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 694: Number of Distinct Islands

link

The challenge is to find a translation-invariant hash function for islands.

We can consider each island having a bounding box around it and then we can translate that bounding box to the top-left of the grid. In this translated bounding box, if for two islands, the sequence of 1-cells are identical, we consider them as duplicate islands.

We visit each 1-cell at most twice, once during explore and once during id generation.

Time: \mathcal{O}(m \cdot n), space: \mathcal{O}(m \cdot n).

from itertools import product as cartesian

class Solution:
    def island_id(self, island, box):
        min_row, max_row, min_col, max_col = box
        row_offset, col_offset = min_row, min_col
        nrow = max_row - min_row + 1
        ncol = max_col - min_col + 1
        
        id = []
        for r, c in cartesian( range(nrow), range(ncol) ):
            if (r+row_offset, c+col_offset) in island:
                id.append(f"{r},{c}")
        return ",".join(id)

    def explore_island(self, row, col, grid, island, box):
        island.append((row, col))
        box[0] = min(box[0], row)
        box[1] = max(box[1], row)
        box[2] = min(box[2], col)
        box[3] = max(box[3], col)

        grid[row][col] = -1
        for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            row2, col2 = row+dr, col+dc
            is_valid_cell = (0 <= row2 < len(grid)) and (0 <= col2 < len(grid[0]))
            if not is_valid_cell or grid[row2][col2] != 1:
                continue

            self.explore_island(row2, col2, grid, island, box)

    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        unique_islands = set()

        m, n = len(grid), len(grid[0])
        for row, col in cartesian( range(m), range(n) ):
            if grid[row][col] != 1:
                continue

            island = []
            box = [float("inf"), float("-inf"), float("inf"), float("-inf")]
            self.explore_island(row, col, grid, island, box)
            unique_islands.add( self.island_id(island, box) )
        
        return len(unique_islands)

Note, we scan the grid top-down, left-right. As a result, for identically shaped islands, we start exploring from the same corner. In other words, if we translated these islands to the top-left of the grid, we would start exploring from the same cell.

So, after the starting cell, the sequence of explored directions would be a good hash function. We just need to mark where we backtracked, like the bottom two examples.

from itertools import product as cartesian

class Solution:
    def explore_island(self, row, col, grid, island_id):
        grid[row][col] = -1
        for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
            row2, col2 = row+dr, col+dc
            is_valid_cell = (0 <= row2 < len(grid)) and (0 <= col2 < len(grid[0]))
            if not is_valid_cell or grid[row2][col2] != 1:
                continue

            island_id.append((dr, dc))
            self.explore_island(row2, col2, grid, island_id)
        
        # Mark backtrack
        island_id.append((0, 0))

    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        unique_islands = set()

        m, n = len(grid), len(grid[0])
        for row, col in cartesian( range(m), range(n) ):
            if grid[row][col] != 1:
                continue

            island_id = []
            self.explore_island(row, col, grid, island_id)
            unique_islands.add( tuple(island_id) )
        
        return len(unique_islands)

tanvirdotzaman

,

Leave a comment