Number of Islands, implementing Depth First Search with the help of minesweeper.
Tags: javascript, tutorial, computerscience, beginners
Published: 2020-04-23 15:41:02

<strong>Problem</strong>
You're given a map of an area, you've to calculate the number of islands in that area. 

What I really like about this problem is that it appears to be an iteration/search-based problem but it's graph-based problem.

Eg if map is : 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/yp9ugbn89i4ko2jr8jru.jpg)

The number of islands will be 3. 

<strong>Solution:</strong>
First, let's convert the map into something more legible: 

```javascript
input : 
[[ 0, 1, 1, 0, 0, 0, 1, 0],
 [ 1, 1, 1, 0, 0, 0, 1, 1],
 [ 1, 1, 1, 0, 0, 1, 1, 1],
 [ 0, 0, 0, 1, 0, 0, 0, 0],
 [ 0, 0, 0, 1, 0, 0, 0, 0],
 [ 0, 0, 1, 1, 0, 0, 0, 0],
 [ 0, 1, 1, 0, 0, 0, 0, 0],
 [ 1, 1, 0, 0, 0, 0, 0, 0]]

where each 1 represents land and each 0 represents the sea. 

A piece of land will be considered as part of the island if it's touching another land from the top, left, right, bottom. 

Island is covered by sea from all sides
```

<strong>Initial thought</strong> 
Initial thought might be to go through each the gird and somehow track the 1's which are connected and determine the number of islands, but that get's messy quickly. 

<strong>MineSweeper</strong> 
When you got your first computer, you might've played minesweeper on it. 
<img src="https://mlexplained.files.wordpress.com/2017/10/minesweeperwin.gif?w=869" />
In the game whenever we clicked on an empty cell, all the adjacent cells were revealed. 

We can use this feature for our problem. We shall traverse the grid if we come across a land cell <strong> "1" </strong>, we will try to look if there's another land cell attached to it. If it's attached then we hop to that land cell and repeat a similar pattern of searching adjacent cells. 

But still, it doesn't solve our problem, we need to figure out a way of not going back to the previous "land" cell.  One way of achieving that is by maintaining a <strong>visited </strong> array or by sinking the land cell by converting it to 0.

Let's go through the processes step by step. 

<strong> 1. Iterate through the grid to find the land </strong> 

```javascript 
let m = grid.length;
let 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){
           // do something
           count++;
        }
     }
}
return count;
```

<strong>2. Let's work on the "do something" part </strong>

<img src = "https://media.giphy.com/media/h3VtmjnkL3v29U2zJw/giphy.gif" />

Blue: visiting the cell for the first time.
Dark Blue: we've gone a level down to the adjacent cell.
Red: Sinking the land so that we don't visit/repeat the same cell again.
Gray: Moving back a level up. 

<strong>Execution</strong>
1> For each cell, we check if it's <strong>1</strong> : land or <strong>0</strong> : sea.
2> If it's 0, we ignore it, if it's 1 we perform our operations. 
3> First operation is to convert the existing cell to 0 so that we dont' visit it again. 
4> Second is to check is neighbours. 
5> If any of it's neighbours are <strong>1</strong> we repeat step 3. 

Let's code this : 
```javascript
var dfs = function(grid,i,j){
  
  // check if current position breaks any of the position constraints 
  if(i<0 || j<0 || i>=grid.length || j==grid[0].length || grid[i][j] == 0) return;
  
  // sink the current land
  grid[i][j] = 0;
  
  // check top
  dfs(grid,i-1,j);

  // check right
  dfs(grid,i,j+1);

  // check bottom
  dfs(grid,i+1,j);

  //check left
  dfs(grid,i,j-1);
}

```

This is basic <strong>Depth First Search Traversal </strong> for each cell, we go a level deeper and keep on doing so till we hit an end condition. In our case the end condition is reached when all the adjacent cells are 0.

<img src = "https://stackabuse.s3.amazonaws.com/media/graph-traversal-in-java-depth-first-search-dfs-1.gif" /> 

Let's put the two codes together. 
```javascript

function numIslands(grid) {
  const H = grid.length;
  const W = H && grid[0].length;
  let count = 0;
  
  for (let r = 0; r < H; r++) {
    for (let c = 0; c < W; c++) {
      if (grid[r][c] === '0') continue;
      
      count++;
      dfs(r, c);
    }
  }
  return count;
  
  function dfs(r, c) {
    if (r < 0 || c < 0 || r === H || c === W) return;
    if (grid[r][c] === '0') return;
    
    grid[r][c] = '0';
    dfs(r-1, c);
    dfs(r+1, c);
    dfs(r, c-1);
    dfs(r, c+1);
  }
}

```

That's it! This is one of the most commonly asked questions during an interview to test your graph skills.

I hope you liked it! 

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/numIslands.js

problem : https://leetcode.com/problems/number-of-islands/