Number of distinct islands ii

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

55.3% acceptance

Mar 31, 2026

280

286

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn num_distinct_islands2(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, cells: &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;
      cells.push((i as i32, j as i32));
      if i + 1 < m { dfs(grid, visited, i + 1, j, cells); }
      if i > 0 { dfs(grid, visited, i - 1, j, cells); }
      if j + 1 < n { dfs(grid, visited, i, j + 1, cells); }
      if j > 0 { dfs(grid, visited, i, j - 1, cells); }
    }
    
    fn normalize(cells: &[(i32, i32)]) -> Vec<(i32, i32)> {
      // 8 transformations: 4 rotations x 2 reflections
      let transforms: Vec<Box<dyn Fn(i32, i32) -> (i32, i32)>> = vec![
        Box::new(|r, c| (r, c)),
        Box::new(|r, c| (r, -c)),
        Box::new(|r, c| (-r, c)),
        Box::new(|r, c| (-r, -c)),
        Box::new(|r, c| (c, r)),
        Box::new(|r, c| (c, -r)),
        Box::new(|r, c| (-c, r)),
        Box::new(|r, c| (-c, -r)),
      ];
      let mut best: Option<Vec<(i32, i32)>> = None;
      for t in &transforms {
        let mut transformed: Vec<(i32, i32)> = cells.iter().map(|&(r, c)| t(r, c)).collect();
        transformed.sort();
        let min_r = transformed[0].0;
        let min_c = transformed[0].1;
        let normalized: Vec<(i32, i32)> = transformed.iter().map(|&(r, c)| (r - min_r, c - min_c)).collect();
        if best.is_none() || normalized < *best.as_ref().unwrap() {
          best = Some(normalized);
        }
      }
      best.unwrap()
    }
    
    for i in 0..m {
      for j in 0..n {
        if grid[i][j] == 1 && !visited[i][j] {
          let mut cells = Vec::new();
          dfs(&grid, &mut visited, i, j, &mut cells);
          let canonical = normalize(&cells);
          shapes.insert(canonical);
        }
      }
    }
    shapes.len() as i32
  }
}