GitHub Repository Submission

When using GitHub mode, paste your repository URL below and click Save URL to store it. The saved URL will be automatically included with every message you send until you choose to clear it. Learn more

Your GitHub repository URL is saved. LSBot will automatically fetch your latest code from this repository for each message. To change the URL, clear it first and save a new one.

Exercise 1

In this problem, as in many other graph problems, we need a way to track visited squares. We used a set to solve this problem. However, do we need a set in this case? Is there another way to mark a square as visited?

Try to solve the problem without using an additional collection like a set. You can always reference the solution provided below.

Think about the type of square we never explore and how we can leverage that.

Solution

In this problem, aside from not exploring out of bounds squares and already visited squares, we are also never exploring an open land square.

While exploring the boundaries of the forest, we can "cut" the forest by converting that square to open land. This way, we ensure that we won't revisit it. If we do this, then every time we encounter a tree square, we can go ahead and increment the forest count. We know that every new tree square is part of a new forest. We don't recommend this approach for counting real forests.

function numOfForests(grid) {
  if (!grid || grid.length === 0) return 0;

  const numRows = grid.length;
  const numCols = grid[0].length;

  function dfs(row, col) {
    if (
      row < 0 || row >= numRows || col < 0 || col >= numCols ||
      grid[row][col] === 'O'
    ) {
      return;
    }

    grid[row][col] = 'O';

    dfs(row, col - 1);
    dfs(row - 1, col);
    dfs(row, col + 1);
    dfs(row + 1, col);
  }

  let forestCount = 0;

  for (let row = 0; row < numRows; row++) {
    for (let col = 0; col < numCols; col++) {
      if (grid[row][col] === 'T') {
        dfs(row, col);
        forestCount++;
      }
    }
  }

  return forestCount;
}

Hi! I'm LSBot. I can help you think through the selected exercise by giving you hints and guidance without revealing the solution. Your code from the editor will be automatically detected. Want to know more? Refer to the LSBot User Guide .

Detected solution
Loading...

Submit your solution for LSBot review.

 Hi! I'm LSBot. Your code from the editor will be automatically detected. I'll review your solution and provide feedback to help you improve. Ask questions about your solution or request a comprehensive code review. Want to know more? Refer to the LSBot User Guide .

Detected solution
Loading...