Making A Large Island

Problem:

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in the grid after applying this operation. An island is a 4-directionally connected group of 1s.

Example,

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.

Approach:

First, let's try to understand the problem. After changing at most one 0 to 1, we have to return the maximum size of a connected component. This connected component is made by only 1. See, we can't count the element that is diagonally connected, we have to count them, those are only connected by 4-directionally.

let's illustrate an example.

Initially, we see here, a total of 3 connected components, and the max size is 3.

After changing one 0 to 1, we found the maximum size of connected components means the biggest Island size is 6.

Now come to the main point, how can we count these connected components and their sizes? Basically, we don't need how many connected components are there, we just need their sizes.

Now, How can we store every connected component's size. See we can mark every component by a specific name.

Suppose first Connected Components elements are 2, then 3, then 4, and so on.

After that, we simply store it in the map by [key, value] pair, like this, mark[2] = 3. Means in 2 components size is 2.

I am trying to say that, we will replace every connected component one(1) with another unique id, like (2,3,4,...etc).

Let's illustrate what happened after changing all components id.

After changing all connected components element we see, have all are different now. Now, they have a unique id.

Using DFS we can do this, every time we will change the id, and count them up.

After changing their id, we can simply consider all zero, which means by brute-forcing(n*m)every time we will check how many id's can be found in 4-directionally.

Hence multiple id can be counted, so will use set, after that simply add their sizes with 1(0 changes to 1 now its included to island). For a better understanding check the code, And code by yourself, because you can't copy this, LOL :D