Making The Largest Island

Approach:

• This is a brute force approach where for every 0 we encounter, we temporarily change it to 1 and find the maximum size of the resulting island that is formed. After finding the size of the island, we will change the 1 back to 0. In the end, we will return the maximum size of the island that we were able to find in all our iterations. We will be using Depth First Search (DFS) to find the islands and their size.

Algorithm:

• We will create the variable ‘maxSize’ intialised to 0 to store our answer, and the variable ‘hasZero’ intialised to the boolean value False to check whether there is at least one zero in the binary matrix.
• We will iterate over the matrix, and for every zero, we temporarily make it one and call the depth-first search at this point.
• Find the maximum size of the island of 1’s and update the ‘maxSize’.
• Again we change the value at that index back to 0.
• Finally, if ‘hasZero’ is true, we will return ‘maxSize’; otherwise, we will return the number N*N  as the grid will have all 1’s belonging to the same island.

Approach:

Let us group the islands by changing the 1s to their index and increment the index. All islands in a particular group have the same index. We store the index and the corresponding size in a map and keep track of the maximum size until now.

Example:

1 0 1 -> 2 0 3
0 1 1 -> 0 3 3
1 0 1 -> 4 0 3

Now, we traverse each 0 in the grid and find its adjacent group and add up their areas. 

For the 0 at (0,1), we get area = m[2]+m[3]+1 = 1+4+1 = 6

For the 0 at (1,0), we get area = m[2]+m[3]+m[4]+1 = 1+4+1+1 = 7

For the 0 at (2, 1), we get area = m[4]+m[3]+1 = 1+4+1 = 6 

We add 1 to account for the converted island.

In the end, we are left with the required answer.

The idea behind the solution is :

• First we give unique id to the all separate components(islands) of 1's and store their sizes as well eg. grid[x][y] = id & size[id] = sz;
• After this, we iterate over every 0 and see what maximum size of the island we can get after flipping it.
• To check how each 0 contributes to the islands, we check its neighbours, see the different id’s they belong to, and then add their respective sizes + 1 (because of 0 being flipped ).

Algorithm:

• Create variables ‘maxSize’ initialized to 0 to store the maximum size of the island, a map ‘islandSize’ to store the size of each component (island), and ‘islandId’ initialized to 2 to give a unique id to each component (island).
• Now first iterate over the grid, and for every 1, find the size of the island through this 1 using the ‘getIslandSize’ function.
• In the ‘getIslandSize’ function, we will be doing the DFS Traversal in all four directions (North, South, East, West) to find the size of the island. Also, we will give that unique id to all the valid locations that can be grouped together.
• Then update the ‘maxSize’ variable, put the ‘islandId’ as a key and size of the component that we get as a value in the map ‘islandSize’.
• Now again, we will iterate over the matrix and for each 0, look at the neighbouring distinct ids seen and add the area of those id’s, plus 1 for the 0 we are toggling. This gives us a candidate answer, and we take the maximum and update the ‘maxSize’ variable.