Islands size Tracking with ID | Explained | C++ | JAVA | Python | 100% BEATS
Intuition & Code Flow
Tag Islands → DFS assigns IDs (2,3,4...) and tracks sizes in key[]
Check Flips → For each '0', sum unique neighbor island sizes using sign
**Intuition & Code Flow**  
1. **Tag Islands** → DFS assigns IDs (2,3,4...) and tracks sizes in `key[]`  
2. **Check Flips** → For each '0', sum unique neighbor island sizes using sign-flip trick  

---

### 🎨 **Example Walkthrough**  
**Original Grid**  
```
1 1 0 1      🟢 🟢  0  🔵  
1 0 0 0  →   🟢  0   0  0  
0 1 1 1       0  🟠 🟠 🟠  
```
**Key Array**: `[3, 1, 2]` (ID 2🟢=3, ID3🔵=1, ID4🟠=3)  

**Flip Center '0' (1,1)**  
Neighbors: 🟢 (up), 🟢 (left), 🟠 (down)  
**Sum**: 3(🟢) + 3(🟠) + 1(flip) = **7**  

---

### 🚨 **Edge Cases**  
1. **All Water (0s)** → Max size = 1  
   ```cpp
   if (key.size() == 0) return 1; // Grid is all 0s
   ```
2. **All Land (1s)** → Max size = n²  
   ```cpp
   return ans == 1 ? n * n : ans; // No 0s to flip
   ```

---

### 🔄 **Sign-Flip Trick Explained**  
- **Step 1**: Add neighbor island size → mark as negative (prevents re-counting)  
- **Step 2**: Reset signs → restore original values for next flip checks  
```cpp
// During flip check:
cnt += key[id];  
key[id] *= -1;   // Mark as used

// After calculation:
key[id] *= -1;   // Reset for next 0-check
```

---

### 🚀 **Code Structure**  
```cpp []
class Solution {
    int d[5] = {1, 0, -1, 0, 1}; // Direction vectors
    int n;

    // Depth-First Search to mark island and calculate its size
    int dfs(int row, int col, int id, vector<vector<int>>& grid) {
        grid[row][col] = id; // Mark cell with island ID
        int cnt = 1; // Initialize size of the island

        for (int i = 0; i < 4; i++) { // Explore all 4 directions
            int nr = row + d[i];
            int nc = col + d[i + 1];

            if (nr >= 0 && nc >= 0 && nr < n && nc < n && grid[nr][nc] == 1)
                cnt += dfs(nr, nc, id, grid);
        }

        return cnt; // Return the total size of the island
    }

public:
    int largestIsland(vector<vector<int>>& grid) {
        n = grid.size(); 
        vector<int> key; // Store sizes of all islands
        int id = 2; // Island IDs start from 2

        // Identify all islands and calculate their sizes
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1)
                    key.push_back(dfs(i, j, id++, grid));
            }
        }

        if (key.empty()) return 1; // Grid contains no land

        int ans = 1;

        // Check all water cells and calculate potential island size
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    int cnt = 1;

                    // Add sizes of neighboring islands
                    for (int k = 0; k < 4; k++) {
                        int nr = i + d[k];
                        int nc = j + d[k + 1];

                        if (nr >= 0 && nc >= 0 && nr < n && nc < n && grid[nr][nc] != 0 && key[grid[nr][nc] - 2] > 0)
                            cnt += key[grid[nr][nc] - 2], key[grid[nr][nc] - 2] *= -1; // Mark island as visited
                    }

                    // Reset the sizes of marked islands
                    for (int k = 0; k < 4; k++) {
                        int nr = i + d[k];
                        int nc = j + d[k + 1];

                        if (nr >= 0 && nc >= 0 && nr < n && nc < n && grid[nr][nc] != 0 && key[grid[nr][nc] - 2] < 0)
                            key[grid[nr][nc] - 2] *= -1; // Unmark island
                    }

                    ans = max(ans, cnt); // Update the largest possible island size
                }
            }
        }

        return ans == 1 ? n * n : ans; // Return result
    }
};
```
``` java []
import java.util.*;

public class Solution {
    private static final int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int largestIsland(int[][] grid) {
        int n = grid.length;
        List<Integer> key = new ArrayList<>();
        int id = 2;

        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, id);
                    key.add(size);
                    id++;
                }
            }
        }

        if (key.isEmpty()) return 1;

        int max = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    Set<Integer> seen = new HashSet<>();
                    int sum = 1;
                    for (int[] dir : dirs) {
                        int ni = i + dir[0];
                        int nj = j + dir[1];
                        if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] >= 2) {
                            int islandId = grid[ni][nj];
                            if (!seen.contains(islandId)) {
                                sum += key.get(islandId - 2);
                                seen.add(islandId);
                            }
                        }
                    }
                    max = Math.max(max, sum);
                }
            }
        }

        return max == 0 ? n * n : max;
    }

    private int dfs(int[][] grid, int i, int j, int id) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
            return 0;
        }
        grid[i][j] = id;
        int count = 1;
        for (int[] dir : dirs) {
            count += dfs(grid, i + dir[0], j + dir[1], id);
        }
        return count;
    }
}
```
``` python []
class Solution(object):
    def largestIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid)
        directions = [ (1,0), (-1,0), (0,1), (0,-1) ]
        key = []
        current_id = 2

        def dfs(i, j, id):
            if i < 0 or j < 0 or i >= n or j >= n or grid[i][j] != 1:
                return 0
            grid[i][j] = id
            count = 1
            for dx, dy in directions:
                count += dfs(i + dx, j + dy, id)
            return count

        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    size = dfs(i, j, current_id)
                    key.append(size)
                    current_id += 1

        if not key:
            return 1

        max_size = 0

        for i in range(n):
            for j in range(n):
                if grid[i][j] == 0:
                    seen = set()
                    current = 1
                    for dx, dy in directions:
                        ni, nj = i + dx, j + dy
                        if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] != 0:
                            island_id = grid[ni][nj]
                            if island_id not in seen:
                                current += key[island_id - 2]
                                seen.add(island_id)
                    max_size = max(max_size, current)

        return max_size if max_size != 0 else n * n
```

**Time**: O(n²) → Two grid passes  
**Space**: O(n²) → DFS stack (worst case)
['Depth-First Search', 'Python', 'C++', 'Java']