You are given an n x n binary matrix grid. You are allowed to change at most one0 to be 1.
Return the size of the largest island ingridafter applying this operation.
An island is a 4-directionally connected group of 1s.
Example 1:
Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Example 2:
Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
Example 3:
Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
Constraints:
n == grid.length
n == grid[i].length
1 <= n <= 500
grid[i][j] is either 0 or 1.
Intuition
Approach:
Treat already cluster of 1s as a whole component,
Make Disjoint set of that
Now for every zero, Try to find adjacent compoenets and add to check if
answer increases
One thing to node *** Size[i] denotes number of nodes in that component in DS
Also, store ultimate parent of all neoghbours in set, while traversing for zeros
To avoid multiple values of same compoenets
Atlast, Traverse again for no zero case, to get final anwer