Leetcode solution - number of islands

Hello everyone , I'm brother watermelon , Today we will do a classic algorithm problem —— Number of Islands .

LeetCode The corresponding title on is 200 topic ：https://leetcode-cn.com/problems/number-of-islands/

This problem belongs to the island problem , There is a fixed routine , That's it Flood fill Algorithm .

Flood fill Algorithm

Flood fill Algorithm is a special algorithm , It's in an area , Spread outward from a certain point and find all the points connected with it , Finally get a block .

The process of covering the whole area from one point , Because it is much like the process of flooding an island , So it was named Flood fill, Literal translation “ Flood filling ”.

The obtained area is often used to fill with new colors . Paint bucket of drawing tool 、 Magic wand tools , It's really just through Flood fill algorithmic .

Implementation is usually DFS （ Depth-first traversal ） or BFS（ Breadth first traversal ）.

Ideas and Implementation

Let's see how to use Flood fill Algorithm to solve this problem .

First we traverse grid Two dimensional array , When the array element is found to be ‘1’, On behalf of us, we visited part of the island , let me put it another way , We found an island , Counter count Add one .

then , We flooded the island , In doing so, all parts of the island are marked “ Visited ”. You can also use an extra size and grid Same visited Array to mark , But it is not necessary to , Unless it is not allowed to modify the original array .

After submergence , We continue to traverse from the original place , Until the end .

DFS The specific code of is implemented as ：

function numIslands(grid: string[][]): number {
    
  const m = grid.length;
  const n = grid[0].length;
  let count = 0;
  for (let i = 0; i < m; i++) {
    
    for (let j = 0; j < n; j++) {
    
      if (grid[i][j] === '1') {
     //  Discover part of the island 
        count++;
        floodFill(grid, i, j);
      }
    }
  }
  return count;
};

function floodFill(grid: string[][], i: number, j: number) {
    
  const m = grid.length; //  common  m  That's ok 
  const n = grid[0].length; //  common  n  Column 
  if (i < 0 || i >= m || j < 0 || j >= n) return; //  Ran out of the map 
  if (grid[i][j] === '0') return; //  Reached the edge of the island 

  grid[i][j] = '0'; //  Flood 
  floodFill(grid, i - 1, j);
  floodFill(grid, i + 1, j);
  floodFill(grid, i, j - 1);
  floodFill(grid, i, j + 1);
}

DFS There is a fatal problem ： When the two-dimensional array is large , There is a risk of stack overflow .

So we might as well implement a BFS Solution method ：

function numIslands(grid: string[][]): number {
    
  const m = grid.length;
  const n = grid[0].length;
  let count = 0;
  for (let i = 0; i < m; i++) {
    
    for (let j = 0; j < n; j++) {
    
      if (grid[i][j] === '1') {
     //  Discover part of the island 
        count++;
        floodFill(grid, i, j);
      }
    }
  }
  return count;
};

function floodFill(grid: string[][], i: number, j: number) {
    
  grid[i][j] = '0';

  const queue: number[][] = [[i, j]];
  while (queue.length) {
    
    const size = queue.length;
    for (let k = 0; k < size; k++) {
    
      const [i, j] = queue.shift();
      fillIfInArea(grid, i - 1, j, queue);
      fillIfInArea(grid, i + 1, j, queue);
      fillIfInArea(grid, i, j - 1, queue);
      fillIfInArea(grid, i, j + 1, queue);
    }
  }
}

function fillIfInArea(grid: string[][], i: number, j: number, queue: number[][]) {
    
  if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return;
  if (grid[i][j] === '0') return;
  grid[i][j] = '0';
  queue.push([i, j]);
}

because JavaScript Native does not provide queues , I'm trying to save trouble , Directly use dynamic array to realize queue , The efficiency of leaving the team is very poor .

Use linked list to implement queue , The performance will be better . If you are interested in implementing a double linked list first , Then implement the queue .

ending

During the interview, I saw the algorithm problems related to the island , Be sure to remember what this article introduces “ Submerged by water , At a loss ” Of Flood fill Algorithm .