1
\$\begingroup\$

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"]
]))

\$\endgroup\$
  • \$\begingroup\$ Instead of using console.log you should rather write real unit tests. The main point is that these unit tests not only contain the input data but also the expected output data. Seeing that the expected output for the first test case is 1, it would be obvious that you define an island as a continuous region of 1's. Your question is missing this very central definition. \$\endgroup\$ – Roland Illig Apr 17 at 20:09
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Unfortunately your function does not work. test array in comment You code counts 5 islands. Counts the large one 3 times, one of the small ones, and counts a zero as a island, and completely misses to other small ones. numIslands("0000000000,0111001111,0001001001,0101001001,0101111011,0000000010,0110011000".split(",").map(i=>i.split(""))) \$\endgroup\$ – Blindman67 Aug 13 '18 at 17:00
  • \$\begingroup\$ You are correct that it counts the large island twice though it does detect the smaller islands correctly. I will have to think about it. \$\endgroup\$ – Marc Rohloff Aug 13 '18 at 20:37
  • \$\begingroup\$ OK, I figured out a better way to do this and updated my code. \$\endgroup\$ – Marc Rohloff Aug 13 '18 at 21:35
  • 1
    \$\begingroup\$ @Rick If you could tell me which parts you are finding confusing and where I should clean it up I would be happy to help out. Deleting it seems a bit extreme don't you think? \$\endgroup\$ – Marc Rohloff Aug 16 '18 at 2:04
  • \$\begingroup\$ @MarcRohloff [["1", "1", "1", "1", "1", "1", "1"], ["0", "0", "0", "0", "0", "0", "1"], ["1", "1", "1", "1", "1", "0", "1"], ["1", "0", "0", "0", "1", "0", "1"], ["1", "0", "1", "0", "1", "0", "1"], ["1", "0", "1", "1", "1", "0", "1"], ["1", "1", "1", "1", "1", "1", "1"]] fails this test \$\endgroup\$ – Rick Sep 11 '18 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.