Making a large island visualization


Speed

Create islands

 

Controls

Speed - increase or decrease the speed of the visualization

Islands- - create islands on the grid.
You can adjust the number of islands generated per click.
- You can also click on the grid cells to create an island.

Start - After adjusting the speed and creating islands, you can now start the visualization to see the workings of the algorithm.

Speed - If the grid becomes to cluttered you can reload it and repeat the above steps.

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.