Plantation

The solution to the problem lies in counting the number of connected components in the GRID using the data structure Disjoint Set Union and now we can check for the contributions of 0s to the number of trees and return the largest group. The implementation for the DSU is as follows:

The steps are as follows : 

Function makeSet(int element, parent[int])

• Assign the parent of the element to itself initially.

Function findSet(int element, parent[int])

• If the parent of the element is storing the element itself
  • Return element.
• Return value assigned to the parent of the element by recursively calling findSet.

Function unionSet(int element1, int element2, [int]parent, [int]rank)

• Assign parent1 with findSet(element1, parent, size).
• Assign parent2 with findSet(element2, parent, size).
• If parent1 and parent2 are not the same
  • Swap parent1 and parent2 if the size of parent1 is less than parent2.
  • Change parent of parent2 to parent1.
  • Add size of parent2 to size of parent1.

Function connectedComp(int N,[int][int]GRID)

• Initialize two arrays parent and rank of length NxN.
• For ‘row’ in range 0 to N
  • For ‘col’ in range 0 to N
    • If GRID[row][col] equal to 1
      • Check for all adjacent cells with a non-zero value in GRID
        1. Call unionSet to perform union.
• Assign answer with maximum value in rank.
• For ‘row’ in range 0 to N
  • For ‘col’ in range 0 to N
    • If GRID[row][col] is 0
      • Maintain a set.
      • Assign sum with 0.
      • Check for all adjacent cells that are valid and have non-zero
        1. If this component is in set
           1. Add rank[component] to sum
           2. Insert the component into the set.
      • Update the maximum value of sum+1 to the answer.
• Return answer.

We can check the contribution of each 0 to its neighboring tree groups and the maximum contributing 0 can be included in our answer.

For each group of trees, we will give them a unique id and map each id with the number of trees in that group. Now we will iterate the GRID and go to each 0, and check for all the 4 directions, if we can get a group of trees then we will increase their count by 1. At last, we can return the largest group of trees formed.

The steps are as follows :

Function DFS( [int][int]GRID , int row , int col , int id , int count)

• If row and col are out of bounds or the GRID[row][col] is 0.
  • We need to return.
• Increase the count by 1.
• Assign GRID[row][col] with ‘id’ .
• Call DFS for all 4 directions.

Function largestGroup (int N, [int][int]GRID )

• Assign id with 2, and answer with 0 initially.
• For ‘row’ in range 0 to N
  • For ‘col’ in range 0 to N
    • If GRID[row][col] equal to 1
      • Call DFS to get the count of trees in the component containing this cell.
      • Map the id and count of this component.
      • Increase id by 1.
      • Update the answer to store the maximum count.
• If answer equal to NxN
  • Return answer.
• For ‘row’ in range 0 to N
  • For ‘col’ in range 0 to N
    • If GRID[row][col] equal to 0
      • Assign ‘sum’ with 1.
      • Check for adjacent cells in all 4 valid directions with non-zero values.
        1. Map the increased counter with id and add it to the sum as shown in the implementation.
        2. Update the maximum value to the answer.
• Return answer.