(BFS +DFS) Simple Solution ✅ | C++| Java | Python | JavaScript
⬆️Upvote if it helps ⬆️Connect with me on Linkedin [Bijoy Sing]BFS solutionDFS SolutionIntuition 🧠When exploring grid-based problems with connected components,
# ⬆️Upvote if it helps ⬆️

---

## Connect with me on Linkedin [Bijoy Sing]

---

# BFS solution

---

```cpp []
class Solution {
public:
    int bfs(int i, int j, vector<vector<int>>& grid) {
        vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        queue<pair<int, int>> q;
        int n = grid.size(), m = grid[0].size();
        q.push({i, j});
        int fish = grid[i][j];
        grid[i][j] = 0;

        while (!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop();
            for (auto d : dir) {
                int a = x + d[0], b = y + d[1];
                if (a >= 0 && a < n && b >= 0 && b < m && grid[a][b]) {
                    q.push({a, b});
                    fish += grid[a][b];
                    grid[a][b] = 0;
                }
            }
        }
        return fish;
    }

    int findMaxFish(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size(), mxFish = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j])
                    mxFish = max(mxFish, bfs(i, j, grid));
        return mxFish;
    }
};
```

```python []
class Solution:
    def bfs(self, i, j, grid):
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        n, m = len(grid), len(grid[0])
        queue = [(i, j)]
        fish = grid[i][j]
        grid[i][j] = 0

        while queue:
            x, y = queue.pop(0)
            for dx, dy in directions:
                a, b = x + dx, y + dy
                if 0 <= a < n and 0 <= b < m and grid[a][b] > 0:
                    queue.append((a, b))
                    fish += grid[a][b]
                    grid[a][b] = 0
        return fish

    def findMaxFish(self, grid):
        n, m = len(grid), len(grid[0])
        mxFish = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] > 0:
                    mxFish = max(mxFish, self.bfs(i, j, grid))
        return mxFish
```


```java []
class Solution {
    public int bfs(int i, int j, int[][] grid) {
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int n = grid.length, m = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        int fish = grid[i][j];
        grid[i][j] = 0;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            for (int[] d : directions) {
                int a = x + d[0], b = y + d[1];
                if (a >= 0 && a < n && b >= 0 && b < m && grid[a][b] > 0) {
                    queue.add(new int[]{a, b});
                    fish += grid[a][b];
                    grid[a][b] = 0;
                }
            }
        }
        return fish;
    }

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


```javascript []
class Solution {
    bfs(i, j, grid) {
        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        const n = grid.length, m = grid[0].length;
        const queue = [[i, j]];
        let fish = grid[i][j];
        grid[i][j] = 0;

        while (queue.length > 0) {
            const [x, y] = queue.shift();
            for (const [dx, dy] of directions) {
                const a = x + dx, b = y + dy;
                if (a >= 0 && a < n && b >= 0 && b < m && grid[a][b] > 0) {
                    queue.push([a, b]);
                    fish += grid[a][b];
                    grid[a][b] = 0;
                }
            }
        }
        return fish;
    }

    findMaxFish(grid) {
        const n = grid.length, m = grid[0].length;
        let mxFish = 0;
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                if (grid[i][j] > 0) {
                    mxFish = Math.max(mxFish, this.bfs(i, j, grid));
                }
            }
        }
        return mxFish;
    }
}
```

---


## DFS Solution 



```cpp []
class Solution {
public:
    int dfs(int i, int j, vector<vector<int>>& grid) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0)
            return 0;
        int fish = grid[i][j];
        grid[i][j] = 0;  // Mark visited
        vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (auto d : dir)
            fish += dfs(i + d[0], j + d[1], grid);
        return fish;
    }

    int findMaxFish(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size(), mxFish = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] > 0)
                    mxFish = max(mxFish, dfs(i, j, grid));
            }
        }
        return mxFish;
    }
};
```


```python []
class Solution:
    def dfs(self, i, j, grid):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
            return 0
        fish = grid[i][j]
        grid[i][j] = 0  # Mark visited
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for dx, dy in directions:
            fish += self.dfs(i + dx, j + dy, grid)
        return fish

    def findMaxFish(self, grid):
        n, m = len(grid), len(grid[0])
        mxFish = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] > 0:
                    mxFish = max(mxFish, self.dfs(i, j, grid))
        return mxFish
```


```java []
class Solution {
    public int dfs(int i, int j, int[][] grid) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0)
            return 0;
        int fish = grid[i][j];
        grid[i][j] = 0;  // Mark visited
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int[] d : directions)
            fish += dfs(i + d[0], j + d[1], grid);
        return fish;
    }

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


```javascript []
class Solution {
    dfs(i, j, grid) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === 0)
            return 0;
        let fish = grid[i][j];
        grid[i][j] = 0;  // Mark visited
        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        for (const [dx, dy] of directions) {
            fish += this.dfs(i + dx, j + dy, grid);
        }
        return fish;
    }

    findMaxFish(grid) {
        const n = grid.length, m = grid[0].length;
        let mxFish = 0;
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < m; j++) {
                if (grid[i][j] > 0) {
                    mxFish = Math.max(mxFish, this.dfs(i, j, grid));
                }
            }
        }
        return mxFish;
    }
}
```
# Intuition 🧠
When exploring grid-based problems with connected components, both DFS and BFS are powerful approaches. Here's why: 
- 🔍 DFS dives deep into each connected region of fish
- 🌊 Perfect for finding isolated groups of fish
- 📊 Helps track total fish count in each connected area
- 🎯 Naturally handles the recursive nature of connected components

# Approach Step by Step 🎯

### Grid Traversal 🔄
1. 🔍 Systematically scan grid cells (i, j)
2. 🎣 When finding fish (grid[i][j] > 0):
   - Initialize fish count
   - Mark cell as visited (set to 0)
   - Start DFS/BFS exploration

### DFS Implementation Details 📝
```cpp
Key Components:
- Direction arrays: {-1,0}, {1,0}, {0,-1}, {0,1}
- Visit marking: grid[i][j] = 0
- Fish counting: sum += grid[i][j]
```

### BFS Alternative 🌊
```cpp
Queue based approach:
- Push start cell (i,j)
- Process neighbors level by level
- Track running sum of fish
```

### Optimization Techniques 🚀
1. In-place modification (grid[i][j] = 0)
   - Saves space
   - Avoids visited array
2. Early termination
   - Skip water cells (0)
   - Boundary checks first

# Complexity Analysis 📈

### Time Complexity ⏱️
- O(n × m) where:
  - n = number of rows
  - m = number of columns
  - Each cell visited exactly once
  - Direction checking: O(1) per cell

### Space Complexity 💾
1. Recursive DFS:
   - O(n × m) worst case
   - Stack depth = size of largest fish region
   
2. Iterative BFS:
   - O(n × m) worst case
   - Queue size = width of fish region


### *If you have questions about implementation details or optimization strategies, feel free to ask! 😊* 💭


['Array', 'Depth-First Search', 'Breadth-First Search', 'Matrix', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']