Javascript recursive solution for count islands

Question

0.00/5 (No votes)

See more:

Trying to understand this recursive solution for the count islands problem.

I lose track after the 4th recursive call since my console.log(grid)
Shows me the next 1 to turn to a 0 is row 3, col 0.
However, my mind says it should've been row 0 col 1.

I know the continue statement breaks an iteration and continues with the next.

grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","1"]
]


function numIslands(grid) {
    const H = grid.length;  // 4
    const W = grid[0].length; // 5

    let count = 0;
    
    for (let r = 0; r < H; r++) { // Row
      for (let c = 0; c < W; c++) { // Col
        if (grid[r][c] === '0') continue;
        
        count++; // 3
        dfs(r, c);
      }
    }
    return count;
    
    function dfs(r, c) { // Gets called first time with (0, 0)

      if (r < 0 || c < 0 || r === H || c === W) return; // Checks if out of bounds.
      if (grid[r][c] === '0') return; 
      console.log("Row: ",  r, "Col: ", c)
      
      grid[r][c] = '0'; // (0, 0) turns from  1 to 0.
      dfs(r-1, c); // (-1, 0) returns due to out of bounds
      dfs(r+1, c); // (1, 0) turns from 1 to 0.
      dfs(r, c-1); // (0, -1) retuns due to out of bounds
      dfs(r, c+1); // 
    }
  }

  console.log(numIslands(grid))

What I have tried:

Testing/breaking this down for a couple of hours +.
Other recursive solutions for this exact problem and understanding them.

Posted 17-Jan-23 21:59pm

Chris Aug2022

Updated 21-Jan-23 17:03pm

Add a Solution

2 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Andre Oosthuizen · Answer 1 · 2023-01-21T04:46:00

Here is an example using a recursive function:

let arr = [{id:1}, {id:2}, {id:3}, {id:4, children:[{id:5}, {id:6}]}];

function countObjects(arr) {
    let count = 0;
    arr.forEach(function(element) {
        if (element.children) {
            count += countObjects(element.children);
        }
        count++;
    });
    return count;
}

console.log(countObjects(arr));

In this example, the countObjects function takes in an array of objects as a parameter. Inside the function, we initialize a count variable to 0. Then we use the forEach method to iterate over each element of the array. If the element has a children property, we call the countObjects function again and pass the children property as an argument. This will recursively count the number of objects in the children array. Then we increment the count by 1, and return the count.

In this example, the output will be 6, as there are 6 objects in the array.

Another way to implement this is using the reduce method

let arr = [{id:1}, {id:2}, {id:3}, {id:4, children:[{id:5}, {id:6}]}];

function countObjects(arr) {
    return arr.reduce((acc, cur) => acc + (cur.children ? countObjects(cur.children) : 0) + 1, 0);
}

console.log(countObjects(arr));

This will also return 6 as the output.

It's important to note that this recursive solution could cause stack overflow if the tree is too deep, so it's important to have a base case to stop the recursion.

Graeme_Grant · Answer 2 · 2023-01-21T17:03:00

I gather that this is not your code. Here is how I read it (without running it)...

0 = off
1 = on

1. dfs is passed a point (r, c).
2. It checks if out of the bounds of the array (recursion only), then we are done.
3. It checks if it is off, then we are done.
4. Sets the cell to off, then it looks in all 4 directions (goto step 1.)

You have 3 Islands.

Javascript recursive solution for count islands

2 solutions

Solution 2

Solution 3

Add your solution here

Preview 0

Javascript recursive solution for count islands

2 solutions

Solution 2

Solution 3

Add your solution here

Preview 0

Existing Members

...or Join us