Number of Distinct Islands
MediumUpdated: Aug 2, 2025
Practice on:
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.
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 ofdistinct islands.
Examples
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.lengthn == grid[i].length1 <= m, n <= 50grid[i][j]is either0or1.
Solution
Method 1 – DFS/BFS with Shape Encoding
Intuition
To count distinct islands, we need to encode the shape of each island in a way that is invariant to translation. The simplest way is to record the relative positions of all cells in an island compared to the starting cell.
Approach
- For each unvisited land cell, start a DFS/BFS and record the path (relative moves or coordinates).
- Store each island's shape in a set to ensure uniqueness.
- The answer is the size of the set.
Code
C++
#include <vector>
#include <set>
using namespace std;
class Solution {
public:
void dfs(vector<vector<int>>& grid, int x, int y, int baseX, int baseY, vector<pair<int,int>>& shape) {
int m = grid.size(), n = grid[0].size();
if (x<0||y<0||x>=m||y>=n||grid[x][y]==0) return;
grid[x][y]=0;
shape.push_back({x-baseX, y-baseY});
dfs(grid,x+1,y,baseX,baseY,shape);
dfs(grid,x-1,y,baseX,baseY,shape);
dfs(grid,x,y+1,baseX,baseY,shape);
dfs(grid,x,y-1,baseX,baseY,shape);
}
int numDistinctIslands(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
set<vector<pair<int,int>>> shapes;
for (int i=0;i<m;++i) for (int j=0;j<n;++j) if (grid[i][j]) {
vector<pair<int,int>> shape;
dfs(grid,i,j,i,j,shape);
shapes.insert(shape);
}
return shapes.size();
}
};
Go
func numDistinctIslands(grid [][]int) int {
m, n := len(grid), len(grid[0])
shapes := map[string]struct{}{}
var dfs func(x, y, baseX, baseY int, shape *[]string)
dfs = func(x, y, baseX, baseY int, shape *[]string) {
if x<0||y<0||x>=m||y>=n||grid[x][y]==0 { return }
grid[x][y]=0
*shape = append(*shape, fmt.Sprintf("%d_%d", x-baseX, y-baseY))
dfs(x+1,y,baseX,baseY,shape)
dfs(x-1,y,baseX,baseY,shape)
dfs(x,y+1,baseX,baseY,shape)
dfs(x,y-1,baseX,baseY,shape)
}
for i:=0;i<m;i++ { for j:=0;j<n;j++ { if grid[i][j]==1 {
shape := []string{}
dfs(i,j,i,j,&shape)
key := strings.Join(shape, ",")
shapes[key]=struct{}{}
}}}
return len(shapes)
}
Java
import java.util.*;
class Solution {
public int numDistinctIslands(int[][] grid) {
int m = grid.length, n = grid[0].length;
Set<String> shapes = new HashSet<>();
for (int i=0;i<m;i++) for (int j=0;j<n;j++) if (grid[i][j]==1) {
List<String> shape = new ArrayList<>();
dfs(grid,i,j,i,j,shape);
shapes.add(String.join(",", shape));
}
return shapes.size();
}
void dfs(int[][] grid, int x, int y, int baseX, int baseY, List<String> shape) {
int m = grid.length, n = grid[0].length;
if (x<0||y<0||x>=m||y>=n||grid[x][y]==0) return;
grid[x][y]=0;
shape.add((x-baseX)+"_"+(y-baseY));
dfs(grid,x+1,y,baseX,baseY,shape);
dfs(grid,x-1,y,baseX,baseY,shape);
dfs(grid,x,y+1,baseX,baseY,shape);
dfs(grid,x,y-1,baseX,baseY,shape);
}
}
Kotlin
class Solution {
fun numDistinctIslands(grid: Array<IntArray>): Int {
val m = grid.size; val n = grid[0].size
val shapes = mutableSetOf<String>()
fun dfs(x: Int, y: Int, baseX: Int, baseY: Int, shape: MutableList<String>) {
if (x<0||y<0||x>=m||y>=n||grid[x][y]==0) return
grid[x][y]=0
shape.add("${x-baseX}_${y-baseY}")
dfs(x+1,y,baseX,baseY,shape)
dfs(x-1,y,baseX,baseY,shape)
dfs(x,y+1,baseX,baseY,shape)
dfs(x,y-1,baseX,baseY,shape)
}
for (i in 0 until m) for (j in 0 until n) if (grid[i][j]==1) {
val shape = mutableListOf<String>()
dfs(i,j,i,j,shape)
shapes.add(shape.joinToString(","))
}
return shapes.size
}
}
Python
class Solution:
def numDistinctIslands(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
shapes = set()
def dfs(x, y, baseX, baseY, shape):
if x<0 or y<0 or x>=m or y>=n or grid[x][y]==0: return
grid[x][y]=0
shape.append((x-baseX, y-baseY))
dfs(x+1,y,baseX,baseY,shape)
dfs(x-1,y,baseX,baseY,shape)
dfs(x,y+1,baseX,baseY,shape)
dfs(x,y-1,baseX,baseY,shape)
for i in range(m):
for j in range(n):
if grid[i][j]:
shape = []
dfs(i,j,i,j,shape)
shapes.add(tuple(shape))
return len(shapes)
Rust
use std::collections::HashSet;
impl Solution {
pub fn num_distinct_islands(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len(); let n = grid[0].len();
let mut grid = grid;
let mut shapes = HashSet::new();
fn dfs(grid: &mut Vec<Vec<i32>>, x: i32, y: i32, base_x: i32, base_y: i32, shape: &mut Vec<(i32,i32)>) {
let m = grid.len() as i32; let n = grid[0].len() as i32;
if x<0||y<0||x>=m||y>=n||grid[x as usize][y as usize]==0 { return; }
grid[x as usize][y as usize]=0;
shape.push((x-base_x, y-base_y));
dfs(grid,x+1,y,base_x,base_y,shape);
dfs(grid,x-1,y,base_x,base_y,shape);
dfs(grid,x,y+1,base_x,base_y,shape);
dfs(grid,x,y-1,base_x,base_y,shape);
}
for i in 0..m as i32 {
for j in 0..n as i32 {
if grid[i as usize][j as usize]==1 {
let mut shape = vec![];
dfs(&mut grid,i,j,i,j,&mut shape);
shapes.insert(shape);
}
}
}
shapes.len() as i32
}
}
TypeScript
function numDistinctIslands(grid: number[][]): number {
const m = grid.length, n = grid[0].length;
const shapes = new Set<string>();
function dfs(x: number, y: number, baseX: number, baseY: number, shape: string[]) {
if (x<0||y<0||x>=m||y>=n||grid[x][y]==0) return;
grid[x][y]=0;
shape.push(`${x-baseX}_${y-baseY}`);
dfs(x+1,y,baseX,baseY,shape);
dfs(x-1,y,baseX,baseY,shape);
dfs(x,y+1,baseX,baseY,shape);
dfs(x,y-1,baseX,baseY,shape);
}
for (let i=0;i<m;i++) for (let j=0;j<n;j++) if (grid[i][j]==1) {
const shape: string[] = [];
dfs(i,j,i,j,shape);
shapes.add(shape.join(","));
}
return shapes.size;
}
Complexity
- ⏰ Time complexity:
O(mn) - 🧺 Space complexity:
O(mn)