Function leetcode_for_rust::cd0200_number_of_islands::num_islands

pub fn num_islands(grid: Vec<Vec<char>>) -> i32

Solutions

Approach 1: Union Find

• Time complexity: O(m*n)

• Space complexity: O(m*n)

• Runtime: 4 ms

• Memory: 4.6 MB

struct UnionFind {
    parents: Vec<i32>,
    count: i32,
    rank: Vec<i32>,
}

impl UnionFind {
    fn new(grid: &Vec<Vec<char>>) -> Self {
        let m = grid.len();
        let n = grid[0].len();
        let mut count = 0;
        let mut parents = vec![-1; m * n];
        let rank = vec![0; m * n];
        for i in 0..m {
            for j in 0..n {
                if grid[i][j] == '1' {
                    parents[i * n + j] = (i * n + j) as i32;
                    count += 1;
                }
            }
        }
        UnionFind { parents: parents, count: count, rank: rank }
    }

    fn find(&mut self, i: i32) -> i32 {
        if self.parents[i as usize] != i {
            self.parents[i as usize] = self.find(self.parents[i as usize])
        };
        self.parents[i as usize]
    }

    fn union(&mut self, x: i32, y: i32) -> i32 {
        let x_parent = self.find(x);
        let y_parent = self.find(y);

        if x_parent == y_parent { return self.count; }

        if self.rank[x_parent as usize] < self.rank[y_parent as usize] {
            self.parents[x_parent as usize] = y_parent;
        } else if self.rank[x_parent as usize] > self.rank[y_parent as usize] {
            self.parents[y_parent as usize] = x_parent;
        } else {
            self.parents[y_parent as usize] = x_parent;
            self.rank[y_parent as usize] += 1;
        }
        self.count -= 1;

        self.count
    }
}

impl Solution {
    pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
        if grid.is_empty() { return 0; }

        let directions: Vec<(i32, i32)> = vec![(-1, 0), (1, 0), (0, -1), (0, 1)];
        let (m, n) = (grid.len(), grid[0].len());
        let mut uf = UnionFind::new(&grid);

        for i in 0..m {
            for j in 0..n {
                if grid[i][j] == '0' { continue; }

                for d in &directions {
                    let (dr, dc) = (i as i32 + d.0, j as i32 + d.1);
                    if dr >= 0 &&
                       dc >= 0 &&
                       dr < m as i32 &&
                       dc < n as i32 &&
                       grid[dr as usize][dc as usize] == '1' {
                        uf.union((i * n + j) as i32, dr * n as i32 + dc);
                    }
                }
            }
        }
        uf.count

    }
}

Approach 2: DFS

• Time complexity: O(m*n)

• Space complexity: O(m*n)

• Runtime: 16ms

• Memory: 4.7MB

use std::collections::HashSet;

impl Solution {
    pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
        if grid.is_empty() { return 0; }

        let mut visited: HashSet<(usize, usize)> = HashSet::new();
        let mut result = 0;
        let m = grid.len();
        let n = grid[0].len();

        for i in 0..m {
            for j in 0..n {
                if !visited.contains(&(i, j)) && grid[i][j] == '1' {
                    Self::dfs(&grid, &mut visited, i, j);
                    result += 1;
                }
            }
        }

        result
    }

    const DIRECTIONS: [[i32; 2]; 4] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    pub fn dfs(grid: &Vec<Vec<char>>, visited: &mut HashSet<(usize, usize)>, m: usize, n: usize) {
        if m >= grid.len() || n >= grid[0].len() || grid[m][n] == '0' || visited.contains(&(m, n)) { return; }

        visited.insert((m, n));
        for dis in Self::DIRECTIONS.iter() {
            let dr = (dis[0] + m as i32) as usize;
            let dc = (dis[1] + n as i32) as usize;
            Self::dfs(grid, visited, dr, dc);
        }
    }
}