200. Number of Islands

Description of Problem

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

Solution

Tags: Depth First Search

Explanation

We use the same manner in 547. Number of Provinces.

Code (Rust)

#[derive(Clone, Copy, Debug, PartialEq)]
enum Colour{
    White,
    Gray,
    Black,
}
use Colour::{White, Gray, Black};

impl Solution {
    pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();

        let mut count = 0;
        let mut colours = vec![ vec![White; n] ; m];
        for i in 0..m {
            for j in 0..n{
                if grid[i][j] == '1' && colours[i][j] == White {
                    Self::dfs((i,j), &grid, &mut colours);
                    count+=1;
                }
            }
        }
        return count;
    }

    fn dfs(node : (usize, usize), grid : &Vec<Vec<char>>, colours : &mut Vec<Vec<Colour>>) {
        let m = grid.len();
        let n = grid[0].len();
        let (i, j) = node;
        colours[i][j] = Gray;
        
        if Self::is_available(&grid, &colours, i-1, j, m, n) {
            colours[i-1][j] = Gray;
            Self::dfs((i-1,j), grid, colours);
        }
        // LEFT
        if Self::is_available(&grid, &colours, i, j-1, m, n) {
            colours[i][j-1] = Gray;
            Self::dfs((i,j-1), grid, colours);
        }
        // RIGHT
        if Self::is_available(&grid, &colours, i, j+1, m, n) {
            colours[i][j+1] = Gray;
            Self::dfs((i,j+1), grid, colours);
        }
        // BOTTOM
        if Self::is_available(&grid, &colours, i+1, j, m, n) {
            colours[i+1][j] = Gray;
            Self::dfs((i+1,j), grid, colours);
        }
        colours[i][j] = Black;
    }

    #[inline(always)]
    fn is_available(
        grid: &Vec<Vec<char>>, 
        colours : &Vec<Vec<Colour>>,
        i : usize,
        j : usize,
        m : usize,
        n : usize
    ) -> bool {
        return 
            0 <= i && i < m 
            && 0 <= j && j < n 
            && grid[i][j] == '1' 
            && colours[i][j] == White
        ;
    }
}

Complexity

Time Complexity

• \( T(m,n) = O(m \cdot n) \)

Auxiliary Space

• \( S(m,n) = O(\min(m,n)) \)