Number of distinct islands

Array Hash Table Depth-First Search Breadth-First Search Union-Find Sorting Matrix Hash Function

62.8% acceptance

Mar 31, 2026

2336

152

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn num_distinct_islands(grid: Vec<Vec<i32>>) -> i32 {
    use std::collections::HashSet;
    let m = grid.len();
    let n = grid[0].len();
    let mut visited = vec![vec![false; n]; m];
    let mut shapes: HashSet<Vec<(i32, i32)>> = HashSet::new();
    
    fn dfs(grid: &Vec<Vec<i32>>, visited: &mut Vec<Vec<bool>>, i: usize, j: usize, base_i: usize, base_j: usize, shape: &mut Vec<(i32, i32)>) {
      let m = grid.len();
      let n = grid[0].len();
      if i >= m || j >= n || visited[i][j] || grid[i][j] == 0 { return; }
      visited[i][j] = true;
      shape.push((i as i32 - base_i as i32, j as i32 - base_j as i32));
      if i + 1 < m { dfs(grid, visited, i + 1, j, base_i, base_j, shape); }
      if i > 0 { dfs(grid, visited, i - 1, j, base_i, base_j, shape); }
      if j + 1 < n { dfs(grid, visited, i, j + 1, base_i, base_j, shape); }
      if j > 0 { dfs(grid, visited, i, j - 1, base_i, base_j, shape); }
    }
    
    for i in 0..m {
      for j in 0..n {
        if grid[i][j] == 1 && !visited[i][j] {
          let mut shape = Vec::new();
          dfs(&grid, &mut visited, i, j, i, j, &mut shape);
          shape.sort();
          shapes.insert(shape);
        }
      }
    }
    shapes.len() as i32
  }
}