Is Number of Distinct Islands II easy or hard?

Number of Distinct Islands II is classified as a Hard problem on LeetCode. The difficulty comes from handling geometric transformations (rotations and reflections) and creating a canonical representation that allows efficient hashing.

Number of Distinct Islands II Python/Java solution

Most solutions use DFS to collect coordinates, generate all rotations and reflections, normalize the coordinates, and store the canonical representation in a hash set. The same logic translates cleanly to Python, Java, and C++ using lists/arrays and hash-based sets.

How to solve Number of Distinct Islands II in O(n)?

Treat the grid traversal as O(m*n). Use DFS to collect island coordinates relative to the starting cell. Generate the 8 rotational and reflection transformations, normalize them, and store the canonical representation in a hash set. This avoids pairwise comparisons between islands.

What is the best approach for Number of Distinct Islands II?

The best approach is DFS with canonical shape hashing. Traverse each island, collect relative coordinates, generate all 8 rotations/reflections, normalize them, and store the smallest representation in a hash set. This ensures islands that differ only by rotation or reflection map to the same canonical signature.

Is Number of Distinct Islands II asked at Google/Amazon/Meta?

Number of Distinct Islands II is a classic grid and hashing problem commonly associated with companies like Google and Meta. It tests graph traversal, shape normalization, and hashing techniques that frequently appear in advanced interview rounds.

What data structure is used in Number of Distinct Islands II?

The main data structures are a hash set to store canonical island signatures and recursion or a stack for DFS traversal. Arrays or lists store island coordinates, which are transformed and normalized before hashing.

What is the time complexity of Number of Distinct Islands II?

The optimal solution runs in O(m * n * K) time, where m and n are grid dimensions and K is the number of cells in an island. DFS visits each cell once, and each island requires generating and normalizing up to 8 transformations.

Description Solution Video 27:55

711. Number of Distinct Islands II

Hard55.3% acceptance2 companiesPremium elsewhere, free here

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.

An island is considered to be the same as another if they have the same shape, or have the same shape after rotation (90, 180, or 270 degrees only) or reflection (left/right direction or up/down direction).

Return the number of distinct islands.

Example 1:

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.

Example 2:

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

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1.

Asked at 2 companies

Amazon

Google

Topics

27:55

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

711. Number of Distinct Islands II

Asked at 2 companies

Topics

Similar problems