BFS vs DFS vs DSU | Pattern Explained | 100% BEATS
Problem SimplifiedFind the largest sum of connected cells in a grid where movement is allowed to adjacent (up/down/left/right) cells.When to Use BFS vs DFS vs D
### **Problem Simplified**  
Find the largest sum of connected cells in a grid where movement is allowed to adjacent (up/down/left/right) cells.  

---

### **When to Use BFS vs DFS vs DSU**  
| **Algorithm** | **Use Case**                                  | **Pros**                                      | **Cons**                                      |
|---------------|-----------------------------------------------|-----------------------------------------------|-----------------------------------------------|
| **DFS**       | Small grids, connected components, simple sum | Easy to code recursively, minimal code       | Stack overflow risk for large grids          |
| **BFS**       | Large grids, shortest path problems           | Avoids stack overflow, level-order traversal | Slightly more code for queue management      |
| **DSU**       | Dynamic connectivity, grouping cells          | Efficient for merging sets                   | Harder to track sums, overkill for simple sums |

**Why DFS Here?**  
- Grid size is small (≤10x10).  
- Directly sum values during traversal.  
- Minimal code (4-6 lines for DFS).  

---

### **Solution Code**  
```cpp []
class Solution {
public:
    int m, n, dir[5] = {-1,0,1,0,-1};

    int dfs(vector<vector<int>>& grid, int i, int j) {
        if (i<0 || i>=m || j<0 || j>=n || !grid[i][j]) return 0;
        int sum = grid[i][j];
        grid[i][j] = 0;
        for (int k=0; k<4; k++)
            sum += dfs(grid, i+dir[k], j+dir[k+1]);
        return sum;
    }

    int findMaxFish(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        int maxFish = 0;
        for (int i=0; i<m; i++)
            for (int j=0; j<n; j++)
                if (grid[i][j])
                    maxFish = max(maxFish, dfs(grid,i,j));
        return maxFish;
    }
};
```
```python []
class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        m, n, dir = len(grid), len(grid[0]), [-1,0,1,0,-1]
        
        def dfs(i,j):
            if i<0 or i>=m or j<0 or j>=n or grid[i][j]==0:
                return 0
            res = grid[i][j]
            grid[i][j] = 0
            for k in range(4):
                res += dfs(i+dir[k], j+dir[k+1])
            return res
        
        max_fish = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    max_fish = max(max_fish, dfs(i,j))
        return max_fish
```

```java []
class Solution {
    int m, n, dir[] = {-1,0,1,0,-1};

    private int dfs(int[][] grid, int i, int j) {
        if (i<0 || i>=m || j<0 || j>=n || grid[i][j]==0) return 0;
        int sum = grid[i][j];
        grid[i][j] = 0;
        for (int k=0; k<4; k++)
            sum += dfs(grid, i+dir[k], j+dir[k+1]);
        return sum;
    }

    public int findMaxFish(int[][] grid) {
        m = grid.length; n = grid[0].length;
        int maxFish = 0;
        for (int i=0; i<m; i++)
            for (int j=0; j<n; j++)
                if (grid[i][j]>0)
                    maxFish = Math.max(maxFish, dfs(grid,i,j));
        return maxFish;
    }
}
```

---

### **Key Notes**  
1. **DFS Direction Array**: `dir = [-1,0,1,0,-1]` simplifies checking 4-directional neighbors.  
   - For each `k` in 0-3: `dir[k]` = row offset, `dir[k+1]` = column offset.  
   - Example: `k=0` → move up (`-1` row), `k=1` → move right (`+1` column).  
2. **Time Complexity**: **O(m×n)** – Every cell is processed once.  
3. **Space Complexity**: **O(m×n)** – Recursion stack depth in worst case (entire grid is one region).  

---

### **Patterns Table**  
| **Pattern**               | **Description**                                                                 | **Example Problems**                                                                 |
|---------------------------|---------------------------------------------------------------------------------|-------------------------------------------------------------------------------------|
| **Connected Components**  | Find groups of connected cells (e.g., islands, ponds).                         | [Max Area of Island](https://leetcode.com/problems/max-area-of-island/)             |
| **Flood Fill**            | Fill a region with a new value based on adjacency.                             | [Flood Fill](https://leetcode.com/problems/flood-fill/)                             |
| **Shortest Path**         | Find the minimum steps to reach a target cell.                                 | [Shortest Path in Binary Matrix](https://leetcode.com/problems/shortest-path-in-binary-matrix/) |
| **Cycle Detection**       | Detect cycles in a grid (e.g., repeated paths).                                | [Detect Cycles in 2D Grid](https://leetcode.com/problems/detect-cycles-in-2d-grid/) |
| **Dynamic Connectivity**  | Track and merge connected regions dynamically.                                 | [Number of Islands II](https://leetcode.com/problems/number-of-islands-ii/)         |
| **Boundary Traversal**    | Traverse or modify cells on the grid boundary.                                 | [Surrounded Regions](https://leetcode.com/problems/surrounded-regions/)             |
| **Level-Order Traversal** | Explore cells level by level (BFS).                                            | [Rotting Oranges](https://leetcode.com/problems/rotting-oranges/)                   |
| **Path Counting**         | Count the number of valid paths in a grid.                                     | [Unique Paths](https://leetcode.com/problems/unique-paths/)                         |
| **Optimization**          | Maximize or minimize a value (e.g., fish, area).                               | [Maximum Number of Fish in a Grid](https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/) |
| **Grouping Cells**        | Group cells based on connectivity or properties.                               | [Count Sub Islands](https://leetcode.com/problems/count-sub-islands/)               |

---

### **15 Similar LeetCode Problems**  
1. [Max Area of Island (DFS/BFS)](https://leetcode.com/problems/max-area-of-island/)  
2. [Number of Islands (DFS/BFS)](https://leetcode.com/problems/number-of-islands/)  
3. [Flood Fill (DFS/BFS)](https://leetcode.com/problems/flood-fill/)  
4. [Rotting Oranges (BFS)](https://leetcode.com/problems/rotting-oranges/)  
5. [Walls and Gates (BFS)](https://leetcode.com/problems/walls-and-gates/)  
6. [Surrounded Regions (DFS)](https://leetcode.com/problems/surrounded-regions/)  
7. [Island Perimeter (DFS)](https://leetcode.com/problems/island-perimeter/)  
8. [Number of Closed Islands (DFS)](https://leetcode.com/problems/number-of-closed-islands/)  
9. [Count Sub Islands (DFS/BFS)](https://leetcode.com/problems/count-sub-islands/)  
10. [Detonate the Maximum Bombs (DFS/BFS)](https://leetcode.com/problems/detonate-the-maximum-bombs/)  
11. [Shortest Path in Binary Matrix (BFS)](https://leetcode.com/problems/shortest-path-in-binary-matrix/)  
12. [As Far from Land as Possible (BFS)](https://leetcode.com/problems/as-far-from-land-as-possible/)  
13. [Nearest Exit from Entrance (BFS)](https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/)  
14. [Minimum Knight Moves (BFS)](https://leetcode.com/problems/minimum-knight-moves/)  
15. [Detect Cycles in 2D Grid (DFS)](https://leetcode.com/problems/detect-cycles-in-2d-grid/)  

**Pattern**: All require traversing connected cells in a grid. DFS/BFS for exploration, DSU for dynamic grouping.
['Depth-First Search', 'Breadth-First Search', 'Union Find', 'Python', 'C++', 'Java']