💥C# | Runtime beats 99.30%, Memory beats 71.13% [EXPLAINED]
Intuition\nYou have a grid with islands (1s) and water (0s). By flipping one 0 to 1, you want to find the largest possible island size.\n\n# Approach\nTrack Isl
# Intuition\nYou have a grid with islands (1s) and water (0s). By flipping one 0 to 1, you want to find the largest possible island size.\n\n# Approach\nTrack Islands:\n\nUse Union-Find to group 1s into islands and keep track of their sizes.\nEvaluate Flips:\n\nFind the largest island initially.\nFor each 0, calculate the potential new island size by flipping it and merging with adjacent islands.\n\n# Complexity\n- Time complexity:\nO(n2) for grid traversal and union-find operations.\n\n- Space complexity:\nO(n2) for Union-Find data structures.\n\n# Code\n```csharp []\npublic class Solution {\n    private static readonly int[] directions = { 0, 1, 0, -1, 0 };\n\n    public int LargestIsland(int[][] grid) {\n        int n = grid.Length;\n        int[] islandSize = new int[n * n + 2]; // Map islandId -> island size, max possible islandId is n * n\n        int islandId = 2; // Start islandId from 2 since grid contains 0 and 1\n        int maxIsland = 0;\n\n        // 1. Mark all islands with unique IDs and calculate their sizes using DFS\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] == 1) {\n                    int size = DFS(grid, i, j, islandId);\n                    islandSize[islandId++] = size;\n                    maxIsland = Math.Max(maxIsland, size); // Track the largest island found so far\n                }\n            }\n        }\n\n        // 2. Try changing each 0 to 1 and calculate the potential maximum island size\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] == 0) {\n                    HashSet<int> seenIslands = new HashSet<int>(); // To avoid counting the same island twice\n                    int newSize = 1; // Start by counting the newly added 1\n\n                    // Check all 4 adjacent cells\n                    for (int d = 0; d < 4; d++) {\n                        int ni = i + directions[d];\n                        int nj = j + directions[d + 1];\n\n                        if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] > 1) {\n                            int id = grid[ni][nj];\n                            if (!seenIslands.Contains(id)) {\n                                newSize += islandSize[id]; // Add the size of the neighboring island\n                                seenIslands.Add(id); // Mark this island as seen\n                            }\n                        }\n                    }\n                    maxIsland = Math.Max(maxIsland, newSize); // Update the largest possible island size\n                }\n            }\n        }\n\n        return maxIsland == 0 ? n * n : maxIsland;\n    }\n\n    // DFS to mark island and calculate its size\n    private int DFS(int[][] grid, int i, int j, int islandId) {\n        int n = grid.Length;\n        grid[i][j] = islandId; // Mark the cell with the islandId\n        int size = 1;\n\n        for (int d = 0; d < 4; d++) {\n            int ni = i + directions[d];\n            int nj = j + directions[d + 1];\n\n            if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] == 1) {\n                size += DFS(grid, ni, nj, islandId); // Accumulate the size of the island\n            }\n        }\n\n        return size;\n    }\n}\n\n```
['Dynamic Programming', 'Union Find', 'Matrix', 'C#']