Easy to understand DFS+BFS solution with the explanation
IntuitionThe problem is to find the largest island in a binary matrix after potentially flipping one 0 to 1. An island is defined as a group of 1s connected eit
# Intuition
The problem is to find the largest island in a binary matrix after potentially flipping one `0` to `1`. An island is defined as a group of `1`s connected either horizontally or vertically (4-directional connectivity).

### Key Observations:
1. **Islands are connected groups of `1`s**: This problem can be thought of as identifying distinct connected components of `1`s. This is similar to a **flood-fill** problem where we need to find the size of connected components.
   
2. **Flipping one `0` to `1`**: We are allowed to flip at most one `0` to `1`. This operation can potentially merge two or more separate islands into a larger island. The goal is to maximize the size of the island formed after this flip.

3. **Existing Solution**: If there are no `0`s, the entire grid is one large island, and the answer is simply the size of the grid. If there are `0`s, we need to check if flipping each `0` creates a larger island by connecting adjacent islands.

4. **Steps**: 
   - First, compute the size of each island using DFS or BFS.
   - Track the size of each island in a map or array.
   - For each `0`, calculate the potential new island size if this `0` is flipped to `1`. To do this, check all 4 adjacent cells and sum up the sizes of the distinct islands that can be connected by this flip.
   - The answer will be the maximum size of the island after flipping one `0` or the largest existing island if no flip results in a larger island.

# Approach
1. **Labeling the Islands**:
   - We will perform a **DFS** to explore and label each island in the grid. Each island will be assigned a unique ID, and its size will be recorded.
   - For each unvisited `1`, initiate a DFS to explore all connected `1`s in the grid and calculate the area of that island. After marking all the cells of this island, we store its size in a map where the key is the island's ID and the value is the island's size.

2. **Tracking the Maximum Island Size**:
   - During the DFS, we also keep track of the **maximum island size** encountered so far. This helps to quickly return the result if the grid contains no `0`s, as the largest island is already found.

3. **Checking the Effect of Flipping Each `0`**:
   - Once all islands are labeled, we check every `0` in the grid. For each `0`, we examine its adjacent cells. If the adjacent cell belongs to a previously discovered island (i.e., it is labeled with a unique ID), we add the size of that island to the potential new island size. We use a **set** to ensure that each adjacent island is counted only once.
   - The new island size after flipping this `0` will be the sum of the sizes of all distinct neighboring islands plus `1` for the flipped cell itself.

4. **Edge Case**:
   - If there are no `0`s in the grid, the largest island is simply the entire grid, and no flipping is necessary.

5. **Return the Largest Island Size**:
   - The final result is the largest island size found from all flips and the existing island sizes.

### Algorithm Steps:
1. Perform a DFS to label each island and calculate its size.
2. Track the maximum size of any island.
3. For each `0`, calculate the potential new island size by considering the islands that can be connected by flipping this `0`.
4. Return the largest island size from the possible flips and the original islands.

# Complexity
- **Time complexity**:
  - **DFS for island labeling**: We perform a DFS traversal for each cell in the grid, which takes \(O(N^2)\), where \(N\) is the number of cells in the grid.
  - **Checking each `0`**: For each `0`, we check its four neighbors and potentially sum the sizes of distinct neighboring islands. This also takes \(O(N^2)\) in the worst case (if we check each cell in the grid).
  - Therefore, the total time complexity is:
    $$O(N^2)$$, where \(N\) is the number of cells (rows or columns).

- **Space complexity**:
  - We use an auxiliary map (or array) to store the size of each island, which takes \(O(N^2)\) space in the worst case (if the grid is filled entirely with `1`s).
  - Additionally, we use a **DFS stack** to store the visited nodes, which also takes \(O(N^2)\) space.
  - Therefore, the total space complexity is:
    $$O(N^2)$$, where \(N\) is the number of cells (rows or columns).

---

### Summary:
- **Time Complexity**: \(O(N^2)\) due to DFS traversal and checking each `0`.
- **Space Complexity**: \(O(N^2)\) for storing island sizes and the visited grid.

This approach ensures that we find the largest island after flipping one `0` to `1` efficiently and handles all edge cases. The use of DFS helps in quickly labeling and calculating the size of islands, and BFS/DFS for flipping `0` ensures that we consider all possible merges.


# Code
```golang []
// Directions for DFS traversal (Right, Left, Down, Up)
var directions = [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

// largestIsland finds the largest possible island by flipping one `0` to `1`
func largestIsland(grid [][]int) int {
	n := len(grid)
	islandID := 2 // Start labeling from 2
	islandSize := map[int]int{}
	
	// DFS function to explore and label an island
	var dfs func(int, int, int) int
	dfs = func(x, y, id int) int {
		// Boundary and visited check
		if x < 0 || y < 0 || x >= n || y >= n || grid[x][y] != 1 {
			return 0
		}
		grid[x][y] = id // Mark the cell with island ID
		size := 1
		for _, dir := range directions {
			size += dfs(x+dir[0], y+dir[1], id)
		}
		return size
	}

	// Step 1: Identify all islands and store their sizes
	maxIsland := 0
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 1 {
				islandSize[islandID] = dfs(i, j, islandID)
				maxIsland = max(maxIsland, islandSize[islandID])
				islandID++
			}
		}
	}

	// Step 2: Try flipping each `0` to `1` and calculate max possible island
	hasZero := false
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 0 {
				hasZero = true
				seen := make(map[int]bool)
				newSize := 1 // Include the flipped cell
				for _, dir := range directions {
					ni, nj := i+dir[0], j+dir[1]
					if ni >= 0 && nj >= 0 && ni < n && nj < n {
						if id, exists := islandSize[grid[ni][nj]]; exists && !seen[grid[ni][nj]] {
							seen[grid[ni][nj]] = true
							newSize += id
						}
					}
				}
				maxIsland = max(maxIsland, newSize)
			}
		}
	}

	// If no `0` was found, return `n * n` (all 1s)
	if !hasZero {
		return n * n
	}
	return maxIsland
}

// Utility function to get the max of two integers
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
```
['Go']