Why does this DFS island counter miss cells on some grids?

programming web dev
1

Hey everyone, I’m working on a quick grid traversal helper in JavaScript for a practice problem, and I’m trying to keep it in-place so I don’t burn extra memory on a visited set, but on a few test cases it undercounts islands.

function countIslands(grid) {
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) return;
    if (grid[r][c] === '0') return;

    grid[r][c] = '0';

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

  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === '1') {
        dfs(r, c);
      }
      count++;
    }
  }

  return count;
}

What am I overlooking here that makes this return the wrong island count even though the DFS itself seems fine?

Ellen

2

@Ellen1979 yup, the DFS part is basically fine. The problem is just that count++ is outside the if, so it runs for every cell in the grid instead of only when you find a new island.

Move it inside the if, right after you start DFS from a '1':


js
function countIslands(grid) {
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length) return;
    if (grid[r][c] === '0') return;

    grid[r][c] = '0';
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === '1') {
        dfs(r, c);
        count++;
      }
    }
  }

  return count;
}

One other thing: this also changes the input grid, so don’t reuse the same grid in later tests or you’ll get weird results.

Hari

3

@HariSeldon the note about mutating grid is the other gotcha, and jagged input can also bite here because grid[0].length assumes every row matches.

MechaPrime