Problem Breakdown

• As in the previous problem "Number of Forests," we are given a grid of Ts (trees) and Os (open land)

• Our goal is to find the largest forest area marked in yellow in the image below.

The key difference from the previous problem is that we're measuring their size instead of counting forests.

In the previous problem, we saw two solutions: one with a set and one without. In this problem, we could also use a set to mark squares as visited.

However, an even better solution is simply converting the tree cell to open land during the depth-first search phase. That way, we wouldn't ever encounter a tree cell that has already been visited when iterating through our rows of cells.

Algorithm

Let's outline the algorithm for the Largest Forest Area problem:

1. Initialize variables

   • Initialize a variable largestForest to to keep track of the size of the largest forest found so far.

2. Iterate through the grid

   • Iterate through each cell in the grid. When we encounter a tree cell ('T'):
     • Start a Depth-First Search (DFS) from this cell to explore the entire forest.

3. Perform Depth-First Search (DFS)

   • Initialize a variable currentForestSize to 0.
   • Check if the current cell is within the grid boundaries and is a tree ('T').
   • If it's a valid tree cell:
     • Convert the cell from 'T' to 'O' (marking it as visited).
     • Increment currentForestSize.
     • Recursively call DFS on all four adjacent cells (up, down, left, right).

4. Update the largest forest size

   • After completing DFS for a forest:
     • Compare currentForestSize with largestForest.
     • If currentForestSize is larger, update largestForest.

5. Return result

   • After iterating through all cells in the grid, return largestForest.

Walkthrough

Let's do a walkthrough on one of the examples from the test cases:

• Step 1: We'll iterate through the grid until we hit the first tree cell.

• Step 2: We hit the first tree cell at (0,1). We perform a depth-first search and mark it and its connected tree (1,1) as visited by converting it to an open land cell. We count the size of this forest (two trees) and set it as our current largest forest.

• Step 3: We continue iteration and find the next unvisited tree at (0,3).

• Step 4: We perform a depth-first search from (0,3), marking it and (0,4) as visited by converting them to open land cells. This forest also has a size of two trees, which equals our current largest forest, so we don't update the largest forest size.

• Step 5: We continue iteration until we hit another tree cell.

• Step 6: In the third row, we find an unvisited tree cell at (2,2). We perform depth-first search to explore that forest. We mark (2,2), (3,2), (3,3), (3,4), (4,2), (4,3), and (4,4) as visited by converting them to open land cells. This forest has a size of seven trees, which is larger than our current largest forest, so we update the largest forest size to seven.

• Step 7: We continue iteration and find our final unvisited tree at (4,0).

• Step 8: We explore this single-cell forest and mark it as visited by converting it to an open land cell. Its size (one tree) is smaller than our largest forest, so the largest forest size remains seven.

• Step 9: We complete our iteration through the grid. All the tree cells have been visited, and we've found that the largest forest area is seven.

function largestForestArea(grid) {
  if (!grid || grid.length === 0) return 0;
  const numRows = grid.length;
  const numCols = grid[0].length;
  let largestForest = 0;
  let currentForestSize = 0;

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

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

  for (let row = 0; row < numRows; row++) {
    for (let col = 0; col < numCols; col++) {
      if (grid[row][col] === 'T') {
        currentForestSize = 0;
        dfs(row, col);
        largestForest = Math.max(largestForest, currentForestSize);
      }
    }
  }

  return largestForest;
}