Is Number of Distinct Islands easy or hard?

Number of Distinct Islands is generally classified as a medium difficulty problem. The grid traversal itself is straightforward, but the challenge is recognizing that island shapes must be normalized before comparison. Using hashing with relative coordinates or DFS path encoding makes the problem manageable.

Number of Distinct Islands Python/Java solution

Implement DFS starting from each unvisited land cell. Track relative coordinates such as (r-baseR, c-baseC) while exploring neighbors. Store the resulting coordinate list or encoded path string in a set. Python uses a set of tuples or strings, while Java typically uses HashSet for shape signatures.

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

Treat the grid as a graph and run DFS or BFS from every unvisited land cell. While exploring an island, record each cell's position relative to the starting cell or record traversal directions. Insert this normalized representation into a hash set. Because each cell is visited once, the total runtime is O(m*n).

What is the best approach for Number of Distinct Islands?

The most common approach uses DFS to traverse each island and record its shape relative to the first cell discovered. Relative coordinates or traversal path signatures are stored in a hash set to detect duplicates. This method runs in O(m*n) time because each grid cell is visited once.

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

Variants of island-counting and grid traversal problems appear frequently in interviews at Google, Amazon, and Meta. Problems like Number of Islands, Distinct Islands, and Island Perimeter test DFS/BFS traversal, hashing of structures, and grid graph reasoning.

What data structure is used in Number of Distinct Islands?

The solution typically uses a hash set to store unique island shapes and a grid traversal structure using DFS or BFS. Relative coordinate lists or traversal strings act as the hash key. Recursion stacks or queues are used to explore connected components in the grid.

What is the time complexity of Number of Distinct Islands?

The optimal solution runs in O(m*n) time where m and n are the grid dimensions. Every cell is processed once during DFS or BFS traversal, and island shapes are stored in a hash set for constant-time lookups. Space complexity is also O(m*n) in the worst case due to recursion and stored shapes.

Description Solution Video 17:43

694. Number of Distinct Islands

Medium62.8% acceptance12 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 and only if one island can be translated (and not rotated or reflected) to equal the other.

Return the number of distinct islands.

Example 1:

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

Example 2:

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

Constraints:

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

Asked at 12 companies

Tiktok Snapchat Coupang Aurora Oracle Walmart Labs ServiceNow Anduril Amazon Microsoft

Google Bloomberg

Topics

17:43

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

Open solution

694. Number of Distinct Islands

Asked at 12 companies

Topics

Similar problems