C# Solution for Making A Large Island Problem
IntuitionThe problem requires us to find the largest island size after flipping at most one 0 to 1 in a binary grid.
If the grid is already all 1s, the answer i
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires us to find the largest island size after flipping at most one 0 to 1 in a binary grid.
1.	If the grid is already all 1s, the answer is the size of the entire grid.
2.	If the grid contains 0s, we need to find the best 0 to flip that maximizes the island size.
3.	Since an island is formed by 4-directionally connected 1s, flipping a 0 can merge multiple islands.

Key Observations:
•	Each 1 belongs to some island, so we need to identify and label islands uniquely.
•	Each 0 can potentially connect multiple neighboring islands.
•	Using DFS, we can find all islands and store their sizes in a hash map for quick lookups.

# Approach
<!-- Describe your approach to solving the problem. -->
Step 1: Identify Islands and Store Their Sizes
	•	Traverse the grid, and for each unvisited 1, perform DFS to mark and find its size.
	•	Assign each island a unique index (starting from 2) to differentiate them.
	•	Store each island’s size in a dictionary (Dictionary<int, int>).

Step 2: Evaluate Each 0 to Find the Maximum Possible Island
	•	Iterate over the grid and check each 0.
	•	Find the unique island indices around this 0 using a HashSet (to avoid double counting).
	•	Sum up the sizes of these islands and add 1 (for the flipped 0 itself).
	•	Keep track of the maximum island size.

Step 3: Return the Largest Possible Island Size
	•	If no 0 is present, return the size of the largest island found in Step 1.
	•	Otherwise, return the maximum computed in Step 2.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
1.	Step 1: Identifying Islands (DFS) → O(n²)
	•	Each cell is visited once, and DFS explores all connected 1s.
	•	Since each island is visited only once, the total DFS cost is O(n²).
2.	Step 2: Checking Each 0 and Computing the New Island Size → O(n²)
	•	Each 0 is checked, and its 4 neighbors are inspected in O(1).
	•	The hash lookup for neighboring islands is O(1).
3.	Total Time Complexity: O(n²)
	•	This is optimal given the constraints (n ≤ 500).

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
1.	DFS Recursion Stack → O(n²) (worst case)
	•	If the grid is entirely filled with 1s, the recursion stack can reach O(n²).
2.	Dictionary to Store Island Sizes → O(n²)
	•	In the worst case, each cell is its own island, requiring O(n²) space.
3.	Modified Grid for Marking Islands → O(1) (in-place modification)

Total Space Complexity: O(n²) (worst case).

# Code
```csharp []
public class Solution {
    public int LargestIsland(int[][] grid) {
        int n = grid.Length;
        int index = 2; 
        Dictionary<int, int> islandSize = new Dictionary<int, int>();
        bool hasZero = false;
        int maxIsland = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    int size = DFS(grid, i, j, index);
                    islandSize[index] = size;
                    maxIsland = Math.Max(maxIsland, size);
                    index++;
                } else {
                    hasZero = true;
                }
            }
        }

        if (!hasZero) return maxIsland;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    HashSet<int> seenIslands = new HashSet<int>();
                    int newSize = 1; 
                    int[][] directions = { new int[]{0, 1}, new int[]{0, -1}, new int[]{1, 0}, new int[]{-1, 0} };

                    foreach (var dir in directions) {
                        int ni = i + dir[0], nj = j + dir[1];

                        if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] > 1) {
                            int islandIndex = grid[ni][nj];

                            if (seenIslands.Add(islandIndex)) { 
                                newSize += islandSize[islandIndex];
                            }
                        }
                    }

                    maxIsland = Math.Max(maxIsland, newSize);
                }
            }
        }

        return maxIsland;
    }
    private int DFS(int[][] grid, int i, int j, int index) {
        int n = grid.Length;
        if (i < 0 || i >= n || j < 0 || j >= n || grid[i][j] != 1) return 0;

        grid[i][j] = index; 
        int size = 1;
        int[][] directions = { new int[]{0, 1}, new int[]{0, -1}, new int[]{1, 0}, new int[]{-1, 0} };
        foreach (var dir in directions) {
            size += DFS(grid, i + dir[0], j + dir[1], index);
        }

        return size;
    }
}
```
['C#']