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

• Roland Illig: 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.

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.

• Blindman67: 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("")))
• Marc Rohloff: 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.
• Marc Rohloff: OK, I figured out a better way to do this and updated my code.
• Marc Rohloff: @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?
• Rick: @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