Islands area Tracking with ID | Explained |  Python | 94% BEATS|Easy solution
IntuitionThe problem being solved here is to find the largest possible island in a binary grid (where 1 represents land and 0 represents water). We are allowed
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem being solved here is to find the largest possible island in a binary grid (where 1 represents land and 0 represents water). We are allowed to flip exactly one 0 into a 1 to maximize the size of the island.
# Approach
<!-- Describe your approach to solving the problem. -->
**Step 1:** Find Connected Components Using BFS

The grid is scanned, and each island (group of connected 1s) is assigned a unique component number x.
We use BFS (Breadth-First Search) to compute the size of each component and store it in area[x].
The comp array keeps track of which component each cell belongs to.

**Step 2:** Check If the Grid is Already Fully Land

If there are no 0s in the grid, return n * n immediately, since the entire grid is already an island.

**Step 3:** Try Flipping Each 0 and Compute Maximum Island Size

For each 0 in the grid:
Check its adjacent 1s and collect their component numbers in a set (k).
Sum up the sizes of these unique connected components from the area array.
Compute the new possible island size and update ans.

**Step 4:** Return the Maximum Possible Island Size

The largest island size found is returned.

**Detailed Walkthrough with an Example:**

Example Input:
```
grid = [[1, 0],
        [0, 1]]

```
Step 1: Find Connected Components

We scan the grid and mark islands using BFS:

The first 1 at (0,0) gets assigned comp=1 and area[1] = 1.
The second 1 at (1,1) gets assigned comp=2 and area[2] = 1.

So, we have:
```
comp = [[1, 0],
        [0, 2]]

area = [-1, 1, 1]

```
Step 2: Check if the Grid is Fully Land

Since there are 0s, we proceed.

Step 3: Try Flipping Each 0

Flipping (0,1) → It touches components {1, 2}, so the new size = 1 + area[1] + area[2] = 3.
Flipping (1,0) → It also touches {1, 2}, giving the same result.
Step 4: Return the Maximum Possible Island Size

The maximum size we can get is 3, so return 3.

**The Edge Cases to check:**

1. Grid is Already Fully Land (1s Only)
```
grid = [[1, 1],
        [1, 1]]

```


2. Grid is Already Fully Water (0s Only)
```
grid = [[0, 0],
        [0, 0]]

```
How is it Handled?

The BFS traversal won't find any 1s to create components.
When iterating over 0s, flipping any one of them will result in an island of size 1.
The answer will be 1 in this case.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
Finding Components (BFS): $$O(n*n) $$
Checking Each 0: $$O(n*n) $$
Overall Complexity:$$O(n*n) $$ which is efficient.

# Code
```python3 []
class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n=len(grid)
        visited=[[0]*n for _ in range(n)]
        comp=[[0]*n for _ in range(n)]
        if n==1:
            return 1
        def bfs(i,j,x):
            ans=0
            que=deque()
            que.append((i,j))
            visited[i][j]=1
        
            while que:
                i,j=que.popleft()
                comp[i][j]=x
                ans+=1
                if i-1>=0 and grid[i-1][j]==1 and not visited[i-1][j]:
                    que.append((i-1,j))
                    visited[i-1][j]=1

                if j-1>=0 and grid[i][j-1]==1 and not visited[i][j-1]:
                    que.append((i,j-1))
                    visited[i][j-1]=1

                if i+1<n and grid[i+1][j]==1 and not visited[i+1][j]:
                    que.append((i+1,j))
                    visited[i+1][j]=1

                if j+1<n and grid[i][j+1]==1 and not visited[i][j+1]:
                    que.append((i,j+1))
                    visited[i][j+1]=1
            return ans

        x=1
        area=[-1]*(n*n)

        for i in range(n):
            for j in range(n):
                if grid[i][j]==1 and not visited[i][j]:
                    area[x]=bfs(i,j,x)
                    x+=1
        flip=0
        for i in range(n):
            for j in range(n):
                if grid[i][j]==0:
                    flip=1
                    break
        if flip==0:return n*n
        ans=1
        for i in range(n):
            for j in range(n):
                k=set()
                if grid[i][j]==0:
                    if i-1>=0 and grid[i-1][j]==1:
                        k.add(comp[i-1][j])
                    if j-1>=0 and grid[i][j-1]==1:
                        k.add(comp[i][j-1])
                    if i+1<n and grid[i+1][j]==1:
                        k.add(comp[i+1][j])
                    if j+1<n and grid[i][j+1]==1:
                        k.add(comp[i][j+1])
                temp=1
                for l in k:
                    temp+=area[l]
                ans=max(ans,temp)
 
        return ans




```
['Python3']