Skip to main content
Talentd

Number of Distinct Islands - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableDepth-First SearchBreadth-First SearchUnion Find5 min readAsked at: Amazon, Microsoft, Oracle +9
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You receive a binary grid where 1 represents land and 0 represents water. Islands are groups of horizontally or vertically connected land cells. The task is to count how many distinct shapes of islands exist in the grid. Two islands are considered the same if their shapes match after translation (shifting position), regardless of where they appear in the grid.

Approach 1: Brute Force Shape Comparison (O((m*n)^2) time, O(m*n) space)

Traverse the grid and collect all cells belonging to each island using a traversal such as Depth-First Search or Breadth-First Search. Store the absolute coordinates of each island's cells. After discovering every island, compare each island's coordinate set against all previously found islands to determine if the shape matches after translation. Normalizing coordinates requires shifting them relative to a base cell before comparison. This works but becomes expensive because every new island may need comparison with many existing shapes.

Approach 2: Relative Coordinate Hashing (O(m*n) time, O(m*n) space)

Instead of storing absolute positions, record each island's cells relative to the first discovered land cell of that island. During a DFS traversal, compute offsets like (row - baseRow, col - baseCol). This converts every island into a normalized shape representation independent of location. Store the sequence of relative coordinates in a set using a Hash Table. If another island produces the same normalized coordinate list, it represents the same shape and will not increase the count. Each cell is visited once, so the traversal runs in linear time.

Approach 3: DFS Path Signature Encoding (O(m*n) time, O(m*n) space)

Another common technique records the traversal path itself. While performing DFS, append characters representing movement directions (for example U, D, L, R) and a marker when backtracking. The resulting traversal string uniquely describes the island's structure. Two islands with identical shapes generate the same traversal signature. Store these signatures in a hash set to count distinct patterns. This avoids storing full coordinate lists and works well with recursive DFS.

Recommended for interviews: DFS with relative coordinate hashing or path signature encoding. Both achieve O(m*n) time by visiting each cell once and storing normalized island shapes in a set. Interviewers expect you to recognize that island position is irrelevant and that the shape must be normalized before hashing. Starting with a brute-force comparison shows understanding, but moving to a hashing-based solution demonstrates strong problem-solving and familiarity with graph traversal.

Solution

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Shape ComparisonO((m*n)^2)O(m*n)Conceptual baseline when learning island problems or validating shape normalization logic
Relative Coordinate Hashing (DFS/BFS)O(m*n)O(m*n)General optimal solution; simple to implement and easy to reason about in interviews
DFS Path Signature EncodingO(m*n)O(m*n)Useful when you prefer storing traversal strings instead of coordinate sets

Video Solution

Amazon Coding Interview Question - Number of Distinct Islands • AlgosWithMichael • 31,850 views views

Watch 9 more video solutions →

Frequently Asked Questions

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<String> 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.

Ready to solve this problem?

Practice Number of Distinct Islands with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Sub Islands

Next

Number of Distinct Islands II