Plantation

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
0 upvote
Asked in company
Inspirisys

Problem statement

Sam is on a plantation drive on his campus. His campus can be represented as an ‘N’x’N’ ‘GRID’ of 0s and 1s. Where cells with 1 represent that there is already a tree and cells with 0 represent that a tree can be planted here.

Sam wants to plant atmost 1 tree in his campus.

Note : It is possible that the grid does not contain any zero.

Return the largest group of trees on the campus after Sam planted 1 tree.

Largest group of trees is the 4-directionally connected group of 1s.

Example: 
Input: ‘N’ = 2 ,'GRID' =  [[0,1],[1,1]]

Output: 4
Explanation:
Sam can plant a tree on the only remaining unplanted cell.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer, ‘T’, denoting the number of test cases.

The first line of each test case contains an integer, 'N’, denoting the size of the (NxN)campus.

The next ‘N’ lines of each test case contain N integers (0 or 1), denoting unplanted and plated area.
Output format : 
Return an integer, denoting the largest group of trees on the campus after Sam planted a tree.
Constraints : 
1  <= T <= 10
1  <= N <= 500
GRID[i][j] is either 0 or 1. 
Time Limit: 1 sec
Sample Input 1 :
2
2
0 1
1 1 
3
1 0 1
0 0 0
0 0 0
Sample Output 1 :
4
3
Explanation Of Sample Input 1 :
Test 1:
Sam can plant a tree on the only remaining unplanted cell.  

Test 2:
Sam can plant a tree between the two trees, so the largest group would contain 3 trees.
Sample Input 2 :
2
2
0 0 
0 0
3
0 1 0
1 0 1
0 1 0
Sample Output 2 :
1
5
Hint

 Check for the connected components using disjoint sets.

Approaches (2)
DSU With path Compression

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.
Time Complexity

O(N^2 x log(N)), Where ‘N’ is the number of rows or columns in the GRID. 

We are performing the union for every element in the NxN GRID.

Hence the time complexity is O(N^2 x log(N)). 

Space Complexity

O( N x N ), Where ‘N’ is the number of rows or columns in the GRID. 

We are maintaining parent and rank arrays, whose length may be NxN in the worst case. 

Hence the space complexity is O( N x N ). 

Code Solution
(100% EXP penalty)
Plantation
Full screen
Console