Number of Islands, implementing Depth First Search with the help of minesweeper.

Problem
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 :

The number of islands will be 3.

Solution:
First, let's convert the map into something more legible:

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

Initial thought
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.

MineSweeper
When you got your first computer, you might've played minesweeper on it.

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 "1" , 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 visited array or by sinking the land cell by converting it to 0.

Let's go through the processes step by step.

1. Iterate through the grid to find the land

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;

2. Let's work on the "do something" part

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.

Execution
1> For each cell, we check if it's 1 : land or 0 : 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 1 we repeat step 3.

Let's code this :

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 Depth First Search Traversal 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.

Let's put the two codes together.

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/