Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/200.html

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'.

Algorithm

Need to use DFS to solve, create a visited array to record whether a certain location has been visited.

For a location that is ‘1’ and has not been visited, recursively enter the number of ‘1’ in its up, down, left, and right positions, assign its visited corresponding value to true, and continue to enter all its adjacent neighbors, so that this Find all the numbers in the connected area, and assign true to the value in the visited.

After finding the adjacent area, increment the result by 1, and then continue to find the next position that is ‘1’ and has not been visited, and so on until the entire original array is traversed.

Or, skipping the visited array to record, just set all visited ‘1’ to be ‘0’. (Assuming we can alter the original array) grid[i][j] = '0';

Code

  • 
    public class Number_of_Islands {
    
        public static void main (String[] args) {
    
            Number_of_Islands out = new Number_of_Islands();
            Solution s = out.new Solution();
    
            System.out.println(s.numIslands(new char[][]{ {'1', '1', '0', '0', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '1', '0', '0'}, {'0', '0', '0', '1', '1'} }));
        }
    
        // from online, directly overrite visited 1s
        public class Solution {
    
            private int n;
            private int m;
    
            public int numIslands(char[][] grid) {
                int count = 0;
                n = grid.length;
                if (n == 0) return 0;
                m = grid[0].length;
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < m; j++)
                        if (grid[i][j] == '1') {
                            dfs(grid, i, j);
                            ++count;
                        }
                }
                return count;
            }
    
            private void dfs(char[][] grid, int i, int j) {
                // @note: grid[i][j] != '1', should last of if(), or else index out of boundary
                if (i < 0 || j < 0 || i >= n || j >= m || grid[i][j] != '1') {
                    return;
                }
    
                grid[i][j] = '0';
                dfs(grid, i + 1, j);
                dfs(grid, i - 1, j);
                dfs(grid, i, j + 1);
                dfs(grid, i, j - 1);
            }
        }
    
        class Solution_bfs {
            public int numIslands(char[][] grid) {
                int h = grid.length; // height
                if (h == 0)
                    return 0;
                int w = grid[0].length; // width
                int count = 0;
    
                boolean[][] visited = new boolean[h][w];
    
                Queue<Integer[]> queue = new LinkedList<>();
                for (int i = 0; i < h; i++) {
                    for (int j = 0; j < w; j++) {
                        if (!visited[i][j] && grid[i][j] == '1') {
                            // No need to clear queue, since previous bfs stops only when queue is empty
                            queue.add(new Integer[]{i, j});
                            BFS(queue, grid, visited);
                            count++;
                        }
                    }
                }
    
                return count;
            }
    
            private void BFS(Queue<Integer[]> queue, char[][] islandGrid, boolean[][] visited) {
    
                int H = islandGrid.length;
                int L = islandGrid[0].length;
    
                while (!queue.isEmpty()) {
    
                    Integer[] x = queue.remove();
                    int row = x[0];
                    int col = x[1];
    
                    if (row < 0 || col < 0 || row >= H || col >= L || visited[row][col] || islandGrid[row][col] != '1')
                        continue;
    
                    visited[row][col] = true;
                    queue.add(new Integer[]{row, (col - 1)});
                    queue.add(new Integer[]{row, (col + 1)});
                    queue.add(new Integer[]{(row - 1), col});
                    queue.add(new Integer[]{(row + 1), col});
                }
            }
        }
    
        // union find
        class Solution_uf {
    
            final int d[][] = { // direction
                {0, 1},
                {1, 0},
                {0, -1},
                {-1, 0}
            };
    
            public int numIslands(char[][] grid) {
                int h = grid.length;
                if (h == 0)
                    return 0;
                int w = grid[0].length;
    
                int N = 0; // id for each point, prepare for UF
                List<Point> ptlist = new ArrayList<Point>(); // each position, Point list
                Map<String, Integer> map = new HashMap<String, Integer>(); // (i,j) => count
    
                for (int i = 0; i < h; i++) {
                    for (int j = 0; j < w; j++) {
                        if (grid[i][j] == '1') {
                            Point pt = new Point(i,j);
                            ptlist.add(pt);
                            map.put(i+","+j, N++);
                        }
                    }
                }
    
                UF uf = new UF(N);
                for (int i = 0; i < N; i++) {
                    Point curr = ptlist.get(i);
                    int row = curr.x;
                    int col = curr.y;
                    for (int k = 0; k < 4; k++) {
                        int x = row + d[k][0];
                        int y = col + d[k][1];
                        if (isValid(grid, h, w, x, y)) {
                            uf.union(i, map.get(x + "," + y));
                        }
                    }
                }
    
                return uf.count();
            }
    
    
            private boolean isValid(char[][] grid, int width, int height, int row, int col) {
                return (row >= 0) && (row < width) && (col >= 0) && (col < height) && grid[row][col] == '1';
            }
    
            class Point {
                int x;
                int y;
    
                public Point(int x, int y) {
                    this.x = x;
                    this.y = y;
                }
            }
        }
    
        class UF {
            private int[] parent;
            private byte[] rank;
            private int count;
    
            public UF(int n) {
                if (n < 0) throw new IllegalArgumentException();
                count = n;
                parent = new int[n];
                rank = new byte[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                    rank[i] = 0;
                }
            }
    
            public int find(int p) {
                validate(p);
                while (p != parent[p]) {
                    parent[p] = parent[parent[p]];
                    p = parent[p];
                }
                return p;
            }
    
            public int count() {
                return count;
            }
    
            public void union(int p, int q) {
                int rootP = find(p);
                int rootQ = find(q);
                if (rootP == rootQ) return;
    
                if      (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
                else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
                else {
                    parent[rootQ] = rootP;
                    rank[rootP]++;
                }
                count--;
            }
    
            private void validate(int p) {
                int n = parent.length;
                if (p < 0 || p >= n) {
                    throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
                }
            }
        }
    
    }
    
    ############
    
    class Solution {
        private char[][] grid;
        private int m;
        private int n;
    
        public int numIslands(char[][] grid) {
            m = grid.length;
            n = grid[0].length;
            this.grid = grid;
            int ans = 0;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '1') {
                        dfs(i, j);
                        ++ans;
                    }
                }
            }
            return ans;
        }
    
        private void dfs(int i, int j) {
            grid[i][j] = '0';
            int[] dirs = {-1, 0, 1, 0, -1};
            for (int k = 0; k < 4; ++k) {
                int x = i + dirs[k];
                int y = j + dirs[k + 1];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                    dfs(x, y);
                }
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/number-of-islands/
    // Time: O(MN)
    // Space: O(MN)
    class UnionFind {
        vector<int> id;
    public:
        UnionFind(int N) : id(N) {
            iota(begin(id), end(id), 0);
        }
        void connect(int x, int y) {
            int a = find(x), b = find(y);
            if (a == b) return;
            id[a] = b;
        }
        int find(int x) {
            return id[x] == x ? x : (id[x] = find(id[x]));
        }
    };
    class Solution {
        int M, N;
        int key(int x, int y) { return x * N + y; }
        int dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
    public:
        int numIslands(vector<vector<char>>& A) {
            if (A.empty() || A[0].empty()) return 0;
            M = A.size(), N = A[0].size();
            UnionFind uf(M * N);
            for (int i = 0; i < M; ++i) {
                for (int j = 0; j < N; ++j) {
                    if (A[i][j] == '0') continue;
                    for (auto &dir : dirs) {
                        int x = i + dir[0], y = j + dir[1];
                        if (x < 0 || y < 0 || x >= M || y >= N || A[x][y] == '0') continue;
                        uf.connect(key(i, j), key(x, y));
                    }
                }
            }
            unordered_set<int> s;
            for (int i = 0; i < M; ++i) {
                for (int j = 0; j < N; ++j) {
                    if (A[i][j] == '0') continue;
                    s.insert(uf.find(key(i, j)));
                }
            }
            return s.size();
        }
    };
    
  • # dfs
    class Solution:
        def numIslands(self, grid: List[List[str]]) -> int:
            def dfs(i, j):
                grid[i][j] = '0'
                for a, b in pairwise(dirs):
                    x, y = i + a, j + b
                    if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
                        dfs(x, y)
    
            ans = 0
            dirs = (-1, 0, 1, 0, -1)
            m, n = len(grid), len(grid[0])
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == '1':
                        dfs(i, j)
                        ans += 1
            return ans
    
    
    # bfs
    from collections import deque
    
    class Solution:
        def numIslands(self, grid: List[List[str]]) -> int:
            if not grid:
                return 0
    
            m, n = len(grid), len(grid[0])
            directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
            islands = 0
    
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == "1":
                        islands += 1
                        q = deque([(i, j)]) # no need to reset q, q already drained from previous bfs
                        while q:
                            x, y = q.popleft()
                            for dx, dy in directions:
                                nx, ny = x + dx, y + dy
                                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == "1":
                                    q.append((nx, ny))
                                    grid[nx][ny] = "0"  # mark as visited
            return islands
    
    
    # union find
    from typing import List, Tuple
    
    class Solution:
    
        def numIslands(self, grid: List[List[str]]) -> int:
            h = len(grid)
            if h == 0:
                return 0
            w = len(grid[0])
    
            N = 0  # id for each point, prepare for UF
            ptlist = []  # each position, Point list
            count_map = {}  # (i,j) => count
    
            for i in range(h):
                for j in range(w):
                    if grid[i][j] == '1':
                        pt = (i, j)
                        ptlist.append(pt)
                        count_map[i, j] = N
                        N += 1
    
            uf = UF(N)
            for i in range(N):
                curr = ptlist[i]
                row, col = curr[0], curr[1]
                for k in range(4):
                    x, y = row + Solution.d[k][0], col + Solution.d[k][1]
                    if self.isValid(grid, h, w, x, y):
                        uf.union(i, count_map[x, y])
    
            return uf.count
    
        def isValid(self, grid: List[List[str]], height: int, width: int, row: int, col: int) -> bool:
            return (row >= 0) and (row < height) and (col >= 0) and (col < width) and grid[row][col] == '1'
    
        d = [  # direction
            (0, 1),
            (1, 0),
            (0, -1),
            (-1, 0)
        ]
    
    class UF:
        def __init__(self, n: int):
            if n < 0:
                raise ValueError("n must be non-negative")
            self.parent = list(range(n))
            self.rank = [0] * n
            self.count = n
    
        def find(self, p: int) -> int:
            self.validate(p)
            while p != self.parent[p]:
                self.parent[p] = self.parent[self.parent[p]]
                p = self.parent[p]
            return p
    
        def count(self) -> int:
            return self.count
    
        def union(self, p: int, q: int):
            rootP = self.find(p)
            rootQ = self.find(q)
            if rootP == rootQ:
                return
    
            if self.rank[rootP] < self.rank[rootQ]:
                self.parent[rootP] = rootQ
            elif self.rank[rootP] > self.rank[rootQ]:
                self.parent[rootQ] = rootP
            else:
                self.parent[rootQ] = rootP
                self.rank[rootP] += 1
            self.count -= 1
    
        def validate(self, p: int):
            n = len(self.parent)
            if p < 0 or p >= n:
                raise ValueError(f"index {p} is not between 0 and {n-1}")
    
    ############
    
    '''
    >>> a = set()
    >>>
    >>> a |= {(1, 1)}
    >>> a
    {(1, 1)}
    >>>
    >>> a |= {(2, 2)}
    >>> a
    {(1, 1), (2, 2)}
    >>>
    >>> a.add((3, 3))
    >>> a
    {(1, 1), (3, 3), (2, 2)}
    >>>
    >>> (1,1) in a
    True
    >>> (10,10) in a
    False
    '''
    class Solution(object):
      def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        visited = set()
        ans = 0
    
        def dfs(grid, i, j, visited):
          if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == "0" or (i, j) in visited:
            return False
          visited |= {(i, j)}
          for di, dj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            newi, newj = i + di, j + dj
            dfs(grid, newi, newj, visited)
          return True
    
        for i in range(0, len(grid)):
          for j in range(0, len(grid[0])):
            if dfs(grid, i, j, visited):
              ans += 1
        return ans
    
    
  • func numIslands(grid [][]byte) int {
    	m, n := len(grid), len(grid[0])
    	var dfs func(i, j int)
    	dfs = func(i, j int) {
    		grid[i][j] = '0'
    		dirs := []int{-1, 0, 1, 0, -1}
    		for k := 0; k < 4; k++ {
    			x, y := i+dirs[k], j+dirs[k+1]
    			if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' {
    				dfs(x, y)
    			}
    		}
    	}
    	ans := 0
    	for i := 0; i < m; i++ {
    		for j := 0; j < n; j++ {
    			if grid[i][j] == '1' {
    				dfs(i, j)
    				ans++
    			}
    		}
    	}
    	return ans
    }
    
  • function numIslands(grid: string[][]): number {
        const m = grid.length;
        const n = grid[0].length;
        let ans = 0;
        function dfs(i, j) {
            grid[i][j] = '0';
            const dirs = [-1, 0, 1, 0, -1];
            for (let k = 0; k < 4; ++k) {
                const x = i + dirs[k];
                const y = j + dirs[k + 1];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                    dfs(x, y);
                }
            }
        }
        for (let i = 0; i < m; ++i) {
            for (let j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    dfs(i, j);
                    ++ans;
                }
            }
        }
        return ans;
    }
    
    
  • using System;
    using System.Collections.Generic;
    using System.Linq;
    
    public class Solution {
        public int NumIslands(char[][] grid)
        {
            var queue = new Queue<Tuple<int, int>>();
            var lenI = grid.Length;
            var lenJ = lenI == 0 ? 0 : grid[0].Length;
            var paths = new int[,] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
            var result = 0;
            for (var i = 0; i < lenI; ++i)
            {
                for (var j = 0; j < lenJ; ++j)
                {
                    if (grid[i][j] == '1')
                    {
                        ++result;
                        grid[i][j] = '0';
                        queue.Enqueue(Tuple.Create(i, j));
                        while (queue.Any())
                        {
                            var position = queue.Dequeue();
                            for (var k = 0; k < 4; ++k)
                            {
                                var next = Tuple.Create(position.Item1 + paths[k, 0], position.Item2 + paths[k, 1]);
                                if (next.Item1 >= 0 && next.Item1 < lenI && next.Item2 >= 0 && next.Item2 < lenJ && grid[next.Item1][next.Item2] == '1')
                                {
                                    grid[next.Item1][next.Item2] = '0';
                                    queue.Enqueue(next);
                                }
                            }
                        }
                    }
                }
            }
            return result;
        }
    }
    
  • const DIRS: [i32; 5] = [-1, 0, 1, 0, -1];
    
    impl Solution {
        pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
            fn dfs(grid: &mut Vec<Vec<char>>, i: usize, j: usize) {
                grid[i][j] = '0';
                for k in 0..4 {
                    let x = i as i32 + DIRS[k];
                    let y = j as i32 + DIRS[k + 1];
                    if x >= 0
                        && (x as usize) < grid.len()
                        && y >= 0
                        && (y as usize) < grid[0].len()
                        && grid[x as usize][y as usize] == '1'
                    {
                        dfs(grid, x as usize, y as usize);
                    }
                }
            }
    
            let mut grid = grid;
            let mut ans = 0;
            for i in 0..grid.len() {
                for j in 0..grid[0].len() {
                    if grid[i][j] == '1' {
                        dfs(&mut grid, i, j);
                        ans += 1;
                    }
                }
            }
            ans
        }
    }
    
    

All Problems

All Solutions