# Maximum Number of Fish in a Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-fish-in-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-fish-in-a-grid
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Matrix
---
## Problem
You are given a **0-indexed** 2D matrix `grid` of size `m x n`, where `(r, c)` represents:

* A **land** cell if `grid[r][c] = 0`, or
* A **water** cell containing `grid[r][c]` fish, if `grid[r][c] > 0`.

A fisher can start at any **water** cell `(r, c)` and can do the following operations any number of times:

* Catch all the fish at cell `(r, c)`, or
* Move to any adjacent **water** cell.

Return _the **maximum** number of fish the fisher can catch if he chooses his starting cell optimally, or_ `0` if no water cell exists.

An **adjacent** cell of the cell `(r, c)`, is one of the cells `(r, c + 1)`, `(r, c - 1)`, `(r + 1, c)` or `(r - 1, c)` if it exists.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-number-of-fish-in-a-grid/image0.png) 

**Input:** grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
**Output:** 7
**Explanation:** The fisher can start at cell `(1,3)` and collect 3 fish, then move to cell `(2,3)` and collect 4 fish.

**Example 2:**

![](https://assets.glich.co/dsa/maximum-number-of-fish-in-a-grid/image1.png) 

**Input:** grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
**Output:** 1
**Explanation:** The fisher can start at cells (0,0) or (3,3) and collect a single fish. 

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 10`
* `0 <= grid[i][j] <= 10`

# Approaches
## Brute-Force Traversal from Every Water Cell
This approach iterates through every cell in the grid. If a cell contains water (i.e., has fish), it is considered a potential starting point. For each such potential starting point, a new traversal (like Depth-First Search or DFS) is initiated to find all reachable water cells and sum up the fish. This process is repeated for every water cell, and the maximum sum found across all starting points is returned.
**Time:** O(m^2 * n^2), where `m` is the number of rows and `n` is the number of columns. The outer loops iterate through all `m * n` cells. For each water cell, we initiate a DFS traversal. In the worst case (a grid full of water), the DFS traversal visits `m * n` cells. This results in a total complexity of `O((m * n) * (m * n))`. · **Space:** O(m * n). For each traversal started from the main loop, a new `visited` array of size `m x n` is created. Additionally, the recursion stack for DFS can go up to `m * n` deep in the worst case (a snake-like path through the grid).
**Pros:** Simple to conceptualize: for every possible start, find the total catch.; Correctly solves the problem.
**Cons:** Highly inefficient due to redundant computations. The same connected component of water is traversed and its fish summed up multiple times, once for each cell within that component.
### Explanation
The main idea is to test every possible starting water cell and calculate the total fish that can be caught from that start.

We initialize a variable `maxFish` to 0. We then loop through each cell `(r, c)` of the `m x n` grid. If `grid[r][c] > 0`, it's a water cell and a valid starting point. From this cell `(r, c)`, we start a traversal to find the total fish in its connected component. To do this, we must keep track of visited cells *for this specific traversal* to avoid infinite loops and recounting fish. So, we create a new `boolean[][] visited` array for each call from the main loop.

A recursive DFS function is a good fit here. The DFS function would take the current cell's coordinates, the grid, and the `visited` array. It would add the fish from the current cell, mark it as visited, and then recursively call itself for all adjacent, unvisited water cells. The sum returned by the traversal from `(r, c)` is compared with `maxFish`, and `maxFish` is updated if the new sum is larger. After checking all cells in the grid, `maxFish` will hold the maximum possible catch.

```java
class Solution {
    public int findMaxFish(int[][] grid) {
        int maxFish = 0;
        int m = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    // For each water cell, start a new traversal
                    boolean[][] visited = new boolean[m][n];
                    int currentFish = dfs(i, j, grid, visited);
                    maxFish = Math.max(maxFish, currentFish);
                }
            }
        }
        return maxFish;
    }

    private int dfs(int r, int c, int[][] grid, boolean[][] visited) {
        int m = grid.length;
        int n = grid[0].length;

        // Check bounds and if the cell is valid (water and not visited)
        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {
            return 0;
        }

        // Mark as visited for this traversal
        visited[r][c] = true;
        int fishCount = grid[r][c];

        // Explore neighbors
        fishCount += dfs(r + 1, c, grid, visited);
        fishCount += dfs(r - 1, c, grid, visited);
        fishCount += dfs(r, c + 1, grid, visited);
        fishCount += dfs(r, c - 1, grid, visited);

        return fishCount;
    }
}
```
### Algorithm
- Initialize `maxFish = 0`.
- Iterate through each cell `(r, c)` from `(0, 0)` to `(m-1, n-1)`.
- If `grid[r][c] > 0`:
    - Create a new `boolean[][] visited` array of size `m x n` and initialize all its values to `false`.
    - Call a traversal function (e.g., DFS) starting from `(r, c)` to calculate the total fish in the connected component. Let this be `currentFish`.
    - The DFS function works as follows:
        - Base case: If the cell is out of bounds, is land, or has been visited, return 0.
        - Mark the current cell as visited.
        - Initialize a local sum with the fish in the current cell.
        - Recursively call DFS for all four adjacent cells (up, down, left, right) and add the results to the local sum.
        - Return the local sum.
    - Update `maxFish = max(maxFish, currentFish)`.
- After the loops complete, return `maxFish`.

## Optimized Traversal (DFS/BFS) with a Visited Set
This is the standard and efficient approach for problems involving connected components on a grid. We iterate through each cell of the grid, but we use a single, global `visited` array to keep track of cells that have already been part of a previously explored component. When we find a water cell that has not been visited yet, we know we've discovered a new, distinct group of connected water cells. We then perform a single traversal (like DFS or BFS) to find the total number of fish in this entire component, marking all its cells as visited along the way. This ensures that each connected component is processed exactly once.
**Time:** O(m * n), where `m` is the number of rows and `n` is the number of columns. Each cell in the grid is visited exactly once by the main loop and the subsequent DFS traversal. The DFS function only explores unvisited cells, so the total work across all DFS calls is proportional to the number of cells in the grid. · **Space:** O(m * n). This is dominated by the space required for the `visited` array. In the worst-case scenario (a long, winding path of water cells), the recursion stack for DFS could also grow to a depth of `O(m * n)`. If using BFS, the queue would require `O(m * n)` space in the worst case.
**Pros:** Optimal time complexity.; Efficient as it processes each connected component only once.; Standard and robust pattern for grid-based connected component problems.
**Cons:** Requires extra space for the `visited` array.
### Explanation
The key optimization is to avoid re-calculating the fish sum for a connected component that has already been explored. This is achieved by using a single `visited` array that persists across the main loop.

We initialize `maxFish = 0` and a `boolean[][] visited` array of size `m x n` to all `false`. We loop through each cell `(r, c)` of the grid. For each cell, we check two conditions: is it a water cell (`grid[r][c] > 0`) AND has it not been visited yet (`!visited[r][c]`)? If both conditions are true, it signifies the start of a new, unexplored connected component. We then initiate a traversal (e.g., DFS) from this cell.

The DFS helper function will explore all reachable water cells, sum their fish, and crucially, mark them as visited in the *shared* `visited` array. The total fish for this component is calculated. Let's call it `currentTotalFish`. We update our global maximum: `maxFish = max(maxFish, currentTotalFish)`. Because the traversal marks all cells in the component as visited, the main loop will skip over them in subsequent iterations, preventing redundant work. This process guarantees that every cell in the grid is visited only once.

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

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Start traversal only if it's a new, unvisited water component
                if (grid[i][j] > 0 && !visited[i][j]) {
                    int currentFish = dfs(i, j, grid, visited);
                    maxFish = Math.max(maxFish, currentFish);
                }
            }
        }
        return maxFish;
    }

    private int dfs(int r, int c, int[][] grid, boolean[][] visited) {
        int m = grid.length;
        int n = grid[0].length;

        // Check bounds and if the cell is valid (water and not visited)
        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {
            return 0;
        }

        // Mark as visited
        visited[r][c] = true;
        int fishCount = grid[r][c];

        // Explore neighbors
        fishCount += dfs(r + 1, c, grid, visited);
        fishCount += dfs(r - 1, c, grid, visited);
        fishCount += dfs(r, c + 1, grid, visited);
        fishCount += dfs(r, c - 1, grid, visited);

        return fishCount;
    }
}
```
### Algorithm
- Initialize `maxFish = 0`.
- Create a `boolean[][] visited` array of size `m x n` and initialize all its values to `false`.
- Iterate through each cell `(r, c)` from `(0, 0)` to `(m-1, n-1)`.
- If `grid[r][c] > 0` and `visited[r][c]` is `false`:
    - This cell is the start of a new, unexplored component.
    - Call a traversal function (e.g., DFS) starting from `(r, c)` to calculate the total fish in this component. Pass the shared `visited` array.
    - The DFS function works as follows:
        - Base case: If the cell is out of bounds, is land, or has been visited, return 0.
        - Mark the current cell as visited in the shared `visited` array.
        - Initialize a local sum with the fish in the current cell.
        - Recursively call DFS for all four adjacent cells and add the results to the local sum.
        - Return the local sum.
    - Let the result of the traversal be `currentTotalFish`.
    - Update `maxFish = max(maxFish, currentTotalFish)`.
- After the loops complete, return `maxFish`.

# Solutions
### Java

```java
class Solution {
private
  int[][] grid;
private
  int m;
private
  int n;
public
  int findMaxFish(int[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] > 0) {
          ans = Math.max(ans, dfs(i, j));
        }
      }
    }
    return ans;
  }
private
  int dfs(int i, int j) {
    int cnt = grid[i][j];
    grid[i][j] = 0;
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {
        cnt += dfs(x, y);
      }
    }
    return cnt;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findMaxFish(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int ans = 0;
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      int cnt = grid[i][j];
      grid[i][j] = 0;
      int dirs[5] = {-1, 0, 1, 0, -1};
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
          cnt += dfs(x, y);
        }
      }
      return cnt;
    };
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j]) {
          ans = max(ans, dfs(i, j));
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution : def findMaxFish ( self , grid : List [ List [ int ]]) -> int : def dfs ( i : int , j : int ) -> int : cnt = grid [ i ][ j ] grid [ i ][ j ] = 0 for a , b in pairwise (( - 1 , 0 , 1 , 0 , - 1 )): x , y = i + a , j + b if 0 <= x < m and 0 <= y < n and grid [ x ][ y ]: cnt += dfs ( x , y ) return cnt m , n = len ( grid ), len ( grid [ 0 ]) ans = 0 for i in range ( m ): for j in range ( n ): if grid [ i ][ j ]: ans = max ( ans , dfs ( i , j )) return ans
```