Update appNew update is available. Click here to update.
sidenav-btnClose
Topic list
Plantation
MEDIUM
20 mins
Other topics
Problem solved
Badge
Skill meter
Strings
-
-
Matrices (2D Arrays)
-
-
Linked List
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Graph
-
-
Dynamic Programming
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
userLevel
Sensei
in DSA topics
Open the topic and solve more problems associated with it to improve your skills
Check out the skill meter for every topic
See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Plantation

Contributed by
imObscure
Medium
yellow-spark
0/80
Avg time to solve 20 mins
Success Rate 65 %
Share
0 upvotes

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, Constraints, Images )
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
Reset Code
Full screen
Auto
copy-code
Console