How hard is LeetCode 711. Number of Distinct Islands II?

LeetCode 711. Number of Distinct Islands II is rated Hard on LeetCode.

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

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

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

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

What topics does LeetCode 711. Number of Distinct Islands II cover?

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

Is LeetCode 711. Number of Distinct Islands II a premium problem?

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

Number of Distinct Islands II — LeetCode 711 Python Solution

HardLeetCode PremiumDepth-First SearchBreadth-First SearchUnion FindHash TableHash Function

Problem: #711
Pattern: Union-Find
Reading time: 7 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,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]
Output: 1
Explanation: The two islands are considered the same because if we make a 180 degrees clockwise rotation on the first island, then two islands will have the same shapes.

Python solution

Python

class Solution:
    def numDistinctIslands2(self, grid: List[List[int]]) -> int:
        def dfs(i, j, shape):
            shape.append([i, j])
            grid[i][j] = 0
            for a, b in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
                    dfs(x, y, shape)

        def normalize(shape):
            shapes = [[] for _ in range(8)]
            for i, j in shape:
                shapes[0].append([i, j])
                shapes[1].append([i, -j])
                shapes[2].append([-i, j])
                shapes[3].append([-i, -j])
                shapes[4].append([j, i])
                shapes[5].append([j, -i])
                shapes[6].append([-j, i])
                shapes[7].append([-j, -i])
            for e in shapes:
                e.sort()
                for i in range(len(e) - 1, -1, -1):
                    e[i][0] -= e[0][0]
                    e[i][1] -= e[0][1]
            shapes.sort()
            return tuple(tuple(e) for e in shapes[0])

        m, n = len(grid), len(grid[0])
        s = set()
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    shape = []
                    dfs(i, j, shape)
                    s.add(normalize(shape))
        return len(s)

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