2
\$\begingroup\$

The task

is taken from leetcode

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:

11110
11010
11000
00000

Output: 1

Example 2:

Input:

11000
11000
00100
00011

Output: 3

My solution

/**
 * @param {character[][]} grid
 * @return {number}
 */
function numIslands(grid) {
  if (grid === null || grid === void 0 || !grid.length || !grid[0].length) { return 0; } 
  const NR = grid.length;
  const NC = grid[0].length;

  const check = (r,c) => {
    if (r < 0 || c < 0 || r >= NR || c >= NC || grid[r][c] === "0" ) { return; }
    grid[r][c] = "0";

    check(r + 1, c);
    check(r - 1, c);
    check(r, c + 1);
    check(r, c - 1);        
  }

  let res = 0;
  for (let r = 0; r < NR; r++) {
    for (let c = 0; c < NC; c++) {
      if (grid[r][c] === "1") {
        res++;        
        check(r,c);
      }
    }
  }
  return res;
};
\$\endgroup\$
3
\$\begingroup\$

I think your algorithm is good. Not much can be done there.

Readability is the last thing people care about when solving puzzles like this, but here on Core Review we do care. So, here's my answer, and it may not be what you expect.

Just remember that readability is good for you. It makes it easier to understand and debug your own code. In the end it will safe you time, especially when the puzzles get a lot harder.

First of all; Variable names need to tell us what they contain, so rowNo instead of r, colNo instead of c. When you've got 10 one-letter variables you will loose track of their meaning.

Too many || conditions in an if () don't improve readability either. Why not use functions like this:

function insideGrid(rowNo, colNo) {
    let insideRow = rowNo >= 0 && rowNo < gridWidth,
        insideCol = colNo >= 0 && colNo < gridHeight;
    return insideRow && insideCol;
}

function onLand(rowNo, colNo) {
    return insideGrid(rowNo, colNo) && grid[rowNo][colNo];
}

Then you can do:

function eraseIsland(rowNo, colNo) {
    if (onLand(rowNo, colNo)) {
        eraseIsland(rowNo - 1, colNo);
        eraseIsland(rowNo + 1, colNo);
        eraseIsland(rowNo, colNo + 1);
        eraseIsland(rowNo, colNo - 1);
    }
}

There is no good reason to use arrow functions, but you can use them for correctly named tiny functions (this is a bit controversial, I know).

An alternative way to walk over the grid is:

let islandCount = 0;
grid.forEach((row, rowNo) => {
    row.foreach((island, colNo) => {
        if (island) {
            islandCount++;
            eraseIsland(rowNo, colNo);
        }
    });
});

Ah, see, I did use arrow functions afteral!

Don't think that shorter code is always better code, it isn't. You could minify your code to one line, like this:

function numIslands(a){if(null===a||void 0===a||!a.length||!a[0].length)return 0;const b=a.length,d=a[0].length,e=(f,g)=>{0>f||0>g||f>=b||g>=d||"0"===a[f][g]||(a[f][g]="0",e(f+1,g),e(f-1,g),e(f,g+1),e(f,g-1))};let f=0;for(let g=0;g<b;g++)for(let b=0;b<d;b++)"1"===a[g][b]&&(f++,e(g,b));return f}

But is that better? I don't think so. As a programmer you're not only writing code for the computer to understand, but also for normal human beings, including yourself.

In summary: Your solution is fine, but the coding could be improved.

(all code published here is untested!)

\$\endgroup\$
  • \$\begingroup\$ +1 for mentioning "readability" and picking up on details. Lately I have been pushing code out for the sake of pushing out code. But some of them are buggy or - as you mentioned - not very readable. However I don't really agree on your statement There is no good reason to use arrow functions. I think if you use them as an anonymous function or as a "class" function, then they are absolutely fine. \$\endgroup\$ – thadeuszlay May 31 at 15:58

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.