MediumNo. 0694LeetCode Premium
Number of Distinct Islands — LeetCode 694 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Hash Table, Hash Function
- 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
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
- Time
- O(n)
- Space · auxiliary
- O(n)
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0721 | Accounts Merge | Medium |
| 0839 | Similar String Groups | Hard |
| 0924 | Minimize Malware Spread | Hard |
| 0928 | Minimize Malware Spread II | Hard |
| 0959 | Regions Cut By Slashes | Medium |
| 1202 | Smallest String With Swaps | Medium |
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.