2658. Maximum Number of Fish in a Grid LeetCode Solution

In this guide, you will get 2658. Maximum Number of Fish in a Grid LeetCode Solution with the best time and space complexity. The solution to Maximum Number of Fish in a Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Number of Fish in a Grid solution in C++
Maximum Number of Fish in a Grid solution in Java
Maximum Number of Fish in a Grid solution in Python
Additional Resources

2658. Maximum Number of Fish in a Grid LeetCode Solution image

Problem Statement of Maximum Number of Fish in a Grid

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:

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:

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

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

2658. Maximum Number of Fish in a Grid LeetCode Solution in C++

class Solution {
 public:
  int findMaxFish(vector<vector<int>>& grid) {
    int ans = 0;

    for (int i = 0; i < grid.size(); ++i)
      for (int j = 0; j < grid[0].size(); ++j)
        if (grid[i][j] > 0)
          ans = max(ans, dfs(grid, i, j));

    return ans;
  }

 private:
  int dfs(vector<vector<int>>& grid, int i, int j) {
    if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
      return 0;
    if (grid[i][j] == 0)
      return 0;
    int caughtFish = grid[i][j];
    grid[i][j] = 0;                                     // Mark 0 as visited
    return caughtFish +                                 //
           dfs(grid, i + 1, j) + dfs(grid, i - 1, j) +  //
           dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
  }
};
/* code provided by PROGIEZ */

2658. Maximum Number of Fish in a Grid LeetCode Solution in Java

class Solution {
  public int findMaxFish(int[][] grid) {
    int ans = 0;

    for (int i = 0; i < grid.length; ++i)
      for (int j = 0; j < grid[0].length; ++j)
        if (grid[i][j] > 0)
          ans = Math.max(ans, dfs(grid, i, j));

    return ans;
  }

  private int dfs(int[][] grid, int i, int j) {
    if (i < 0 || i == grid.length || j < 0 || j == grid.length)
      return 0;
    if (grid[i][j] == 0)
      return 0;
    int caughtFish = grid[i][j];
    grid[i][j] = 0;                                 // Mark 0 as visited
    return caughtFish +                             //
        dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + //
        dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
  }
}
// code provided by PROGIEZ

2658. Maximum Number of Fish in a Grid LeetCode Solution in Python

class Solution:
  def findMaxFish(self, grid: list[list[int]]) -> int:
    def dfs(i: int, j: int) -> int:
      if i < 0 or i == len(grid) or j < 0 or j == len(grid[0]):
        return 0
      if grid[i][j] == 0:
        return 0
      caughtFish = grid[i][j]
      grid[i][j] = 0  # Mark 0 as visited
      return (caughtFish +
              dfs(i + 1, j) + dfs(i - 1, j) +
              dfs(i, j + 1) + dfs(i, j - 1))

    return max(dfs(i, j)
               for i in range(len(grid))
               for j in range(len(grid[0])))
 # code by PROGIEZ