DFS Concept✅|| ⚡Runtime 5 ms || Java Approach 👍
IntuitionThe problem involves finding the maximum number of fish in connected regions of a grid. Each cell in the grid represents water, and the value in the ce
![image.png](https://assets.leetcode.com/users/images/155cfb20-e461-4e4f-a26b-724db630404b_1738042828.6882236.png)


# Intuition

The problem involves finding the maximum number of fish in connected regions of a grid. Each cell in the grid represents water, and the value in the cell represents the number of fish. Connected regions are formed by adjacent cells (up, down, left, right) that contain fish. The goal is to explore all such regions and find the one with the maximum total fish.

My first thought is to use a graph traversal algorithm (either DFS or BFS) to explore all connected cells starting from each unvisited cell that contains fish. By keeping track of visited cells, we can ensure that each region is processed only once.

---

# Approach

1. **Initialization**:
   - Store the grid and its dimensions.
   - Use a `visited` matrix to keep track of cells that have already been processed.
   - Initialize a variable `maxFish` to store the maximum fish count found so far.

2. **Grid Traversal**:
   - Iterate through each cell in the grid.
   - If a cell contains fish (`grid[r][c] > 0`) and has not been visited, start a DFS or BFS from that cell to explore the entire connected region.

3. **DFS/BFS Exploration**:
   - During the traversal, mark cells as visited and accumulate the total fish in the current region.
   - Update `maxFish` if the current region's fish count is greater than the previously recorded maximum.

4. **Return Result**:
   - After processing all cells, return the value of `maxFish`.

---

# Implementation

Here is the step-by-step implementation of the solution using **DFS**:

1. **Class and Variables**:
   - Define the `Solution` class.
   - Declare instance variables for the grid, visited matrix, and grid dimensions (`m` and `n`).

2. **Main Method (`findMaxFish`)**:
   - Initialize the grid, dimensions, and `visited` matrix.
   - Iterate through each cell in the grid.
   - If a cell contains fish and is unvisited, call the `dfs` method to explore the connected region and update `maxFish`.

3. **DFS Method**:
   - Check if the current cell is out of bounds, has no fish, or has already been visited. If so, return `0`.
   - Mark the current cell as visited.
   - Accumulate the fish count in the current cell.
   - Recursively call `dfs` for all four neighboring cells (up, down, left, right).
   - Return the total fish count for the current region.

---

# Complexity

- **Time Complexity**:
  - The algorithm visits each cell in the grid exactly once. For each cell, it performs a constant amount of work (checking boundaries, marking as visited, and exploring neighbors).
  - Therefore, the time complexity is **O(m × n)**, where `m` is the number of rows and `n` is the number of columns in the grid.

- **Space Complexity**:
  - The `visited` matrix requires **O(m × n)** space.
  - The recursion stack for DFS can go up to **O(m × n)** in the worst case (e.g., when the entire grid is one connected region).
  - Therefore, the space complexity is **O(m × n)**.


# Code
```java []
class Solution {
    private int[][] grid;
    private boolean[][] visited;
    private int m, n;

    public int findMaxFish(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        this.visited = new boolean[m][n];
        int maxFish = 0;

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] > 0 && !visited[r][c]) {
                    int currentFish = dfs(r, c);
                    maxFish = Math.max(maxFish, currentFish);
                }
            }
        }

        return maxFish;
    }

    private int dfs(int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0 || visited[r][c]) {
            return 0;
        }

        visited[r][c] = true;
        int fish = grid[r][c];

        // Explore all four directions
        fish += dfs(r + 1, c);
        fish += dfs(r - 1, c);
        fish += dfs(r, c + 1);
        fish += dfs(r, c - 1);

        return fish;
    }
}

```

# Upvote, if you liked the approach
['Array', 'Math', 'Depth-First Search', 'Java']