Getting the maximum island
We are given a binary grid(matrix) map of '1's and '0's(water).
We are allowed to change at most one '0' t0 be '1'(flip one '0' to '1').
Return the size of the largest island in the grid after applying the above opperation.
In this case an island is classified as a 4-directionally connected group of
1s.
In this dfs approach for every 0 encountered, we temporarily change if to a
1
and
estimate the
maximum island formed.
After finding the size we change the 1 back to a 0.
Finally
we
will have the maximum island which we return.
Algorithm
1. Traverse the entire grid swapping 1s for each island with an assigned group id(representing that island).
2. Create a hashmap with mapId as key and size of island as value(this done in the first traversal).
3. Traverse the grid for the ssecond time and find the 0s.
4. Calculate the suns of all neighbors(4-directional) and add 1 to represent the flipped 0.
5. Determine the maximum island by comparing previous sizes.
6. If max is 0 after both traversals, return grid size, this is one big island.
Computational complexity
This algorithm takes O(M + N) where M is the number of rows and N is the number of columns. The space complexity is O(L) where L is the size of the largest island.