Count number of islands 2d grid This is a recursive approach using DFS to counting the number of islands. However, I would like to improve performance, while keeping the code clean concise and readable. Better yet can this be solved using bitwise operations?



var numIslands = function(grid) {

  const search = (row, col, grid) =&gt; {
    if (row &lt; 0 || col &lt; 0 ||
      row &gt; grid.length - 1 || col &gt; grid[row].length - 1 ||
      grid[row][col] === '0') {
      return;
    }
    grid[row][col] = '0';
    search(row - 1, col, grid);
    search(row, col - 1, grid);
    search(row + 1, col, grid);
    search(row, col + 1, grid);
  }
  let count = 0;
  grid.forEach((row, index) =&gt; {
    row.forEach((value, i) =&gt; {
      if (value === "1") {
        search(index, i, grid)
        count++
      }
    })
  })
  return count
}
console.log(numIslands([
  ["1", "1", "1"],
  ["1", "1", "0"],
  ["1", "1", "1"],
  ["0", "1", "0"],
  ["1", "1", "1"]
]))

console.log(numIslands([
  ["1", "1", "1"],
  ["0", "0", "0"],
  ["1", "1", "1"],
  ["0", "0", "0"],
  ["1", "1", "1"]
]))
So the logic I used was to check if a cell is part of an existing island either to above (n) or to the left (w). I came up with three possibilities:


Neither n nor w is an island so start a new island, record the islands number and increment the count.
Only one of the adjoining cells is an island or both are the same island so just add it to the same island.
The adjoining cells are from different islands, merge the islands by decrementing the count.


Something like this:



let numIslands = function(grid) {
  logGrid('input', grid);

  let count = 0;
  let work = [];
  let islandNo = 0;

  grid.forEach((row, rowi) =&gt; {
    work.push( (new Array(row.length)).fill(undefined) );
    row.forEach((value, coli) =&gt; {
      if (value !== '1')
       return;

      let n       = rowi &gt; 0 ? work[rowi-1][coli] : undefined;
      let w       = work[rowi][coli-1];
      let type;

      if (n===undefined &amp;&amp; w===undefined) {
        type  = 'new  ';
        islandNo++;
        work[rowi][coli] = islandNo;
        count++;
      } else if (n===w || n===undefined || w===undefined) {
        type = 'exist';
        work[rowi][coli] = n || w;
      } else /* n !== w */ {
        type  = 'merge';
        work[rowi][coli] = n || w;
        count--;
      }

      // console.log(type, rowi, coli, work[rowi][coli] );

    })
  })
  logGrid('work', work);
  return count
}

   let logGrid = function(title, grid) {
 console.log('------------');
 console.log(title);
 console.log('------------');
 console.log( grid.map(r=&gt; r.map(r=&gt;r||'.').join('')).join("\n"));
 console.log('------------');
   }

   let test = function(grid) {
 grid = grid.map (r =&gt; r.replace(/0/g,'.').split("") );
 console.log( numIslands(grid) );
 console.log();
   }

test(['111',
      '11.',
      '111',
      '.1.',
      '111'  ]);

test(['111',
      '...',
      '111',
      '...',
      '111' ]);

test(['0000000000',
      '0111001111',
      '0001001001',
      '0101001001',
      '0101111011',
      '0000000010',
      '0110011000' ] );




Note that I don't consider diagonally adjacent cells to be the same island and this algorithm probably doesn't handle all situations well, especially hollow islands.
Just a styistic note. Use either var or let, but don't mix the two.