Count number of islands 2d grid

Question

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) => {
    if (row < 0 || col < 0 ||
      row > grid.length - 1 || col > 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) => {
    row.forEach((value, i) => {
      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"]
]))

Answer 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) => {
    work.push( (new Array(row.length)).fill(undefined) );
    row.forEach((value, coli) => {
      if (value !== '1')
       return;

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

      if (n===undefined && 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=> r.map(r=>r||'.').join('')).join("\n"));
 console.log('------------');
   }

   let test = function(grid) {
 grid = grid.map (r => 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.