How hard is LeetCode 694. Number of Distinct Islands?

LeetCode 694. Number of Distinct Islands is rated Medium on LeetCode.

What is the time complexity of LeetCode 694. Number of Distinct Islands?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 694. Number of Distinct Islands?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 694. Number of Distinct Islands cover?

LeetCode 694. Number of Distinct Islands is tagged Depth-First Search, Breadth-First Search, Union Find, Hash Table and Hash Function on LeetCode.

Is LeetCode 694. Number of Distinct Islands a premium problem?

Yes. LeetCode 694. Number of Distinct Islands is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Number of Distinct Islands — LeetCode 694 Python Solution

MediumLeetCode PremiumDepth-First SearchBreadth-First SearchUnion FindHash TableHash Function

Problem: #694
Pattern: Union-Find
Reading time: 4 min
Source: leetcode.com

The problem

You are given an m x n binary matrix grid. 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.

Example

Input: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
Output: 1

Python solution

Python

class Solution:
    def numDistinctIslands(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int, k: int):
            grid[i][j] = 0
            path.append(str(k))
            dirs = (-1, 0, 1, 0, -1)
            for h in range(1, 5):
                x, y = i + dirs[h - 1], j + dirs[h]
                if 0 <= x < m and 0 <= y < n and grid[x][y]:
                    dfs(x, y, h)
            path.append(str(-k))

        paths = set()
        path = []
        m, n = len(grid), len(grid[0])
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x:
                    dfs(i, j, 0)
                    paths.add("".join(path))
                    path.clear()
        return len(paths)

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 694. Number of Distinct Islands is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 694. Number of Distinct Islands?: LeetCode 694. Number of Distinct Islands is rated Medium on LeetCode.
What is the time complexity of LeetCode 694. Number of Distinct Islands?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 694. Number of Distinct Islands?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 694. Number of Distinct Islands cover?: LeetCode 694. Number of Distinct Islands is tagged Depth-First Search, Breadth-First Search, Union Find, Hash Table and Hash Function on LeetCode.
Is LeetCode 694. Number of Distinct Islands a premium problem?: Yes. LeetCode 694. Number of Distinct Islands is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.