LeetCode 2658 - Maximum Number of Fish in a Grid

The problem provides a 2D grid representing a map of land and water cells. Each cell can either be land (value 0) or water containing a positive number of fish.

leetcodemediumarraydepth-first-searchbreadth-first-searchunion-findmatrix

LeetCode Problem 2658

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Solution

Problem Understanding

The problem provides a 2D grid representing a map of land and water cells. Each cell can either be land (value 0) or water containing a positive number of fish. The goal is to determine the maximum number of fish a fisher can collect by starting from any water cell and moving only to adjacent water cells. Adjacent cells are defined as directly up, down, left, or right from the current position.

The input grid dimensions are small (1 <= m, n <= 10) and each cell contains 0 <= grid[i][j] <= 10. The constraints imply that brute-force approaches may work for small inputs but should still be optimized. The output is a single integer, the maximum fish count obtainable. If the grid contains no water, the function should return 0. Important edge cases include grids with all land, grids with isolated water cells, and grids where the optimal path requires traversing multiple connected water cells.

Approaches

The brute-force approach would attempt to start from every water cell and explore all possible paths using backtracking, summing fish values along the way. This guarantees correctness but can be inefficient because it revisits many paths multiple times.

The key insight is that fish can only be collected along connected components of water. Therefore, it is sufficient to calculate the total fish in each connected component of water using either depth-first search (DFS) or breadth-first search (BFS) and track the maximum total. This avoids redundant exploration and ensures we efficiently compute the optimal solution.

Approach Time Complexity Space Complexity Notes
Brute Force O((m_n) * 4^(m_n)) O(m*n) Explore all paths from all water cells, too slow
Optimal (DFS/BFS per component) O(m*n) O(m*n) Visit each cell once, sum fish per connected component

Algorithm Walkthrough

  1. Initialize a variable max_fish to store the maximum number of fish collected across all components.
  2. Define a recursive DFS function that takes the current cell coordinates. If the cell is out of bounds or is land, return 0. Otherwise, mark the cell as visited by setting it to 0, then recursively explore all four adjacent cells (up, down, left, right), summing the fish collected.
  3. Iterate through all cells in the grid. For each water cell (value > 0), call the DFS function starting from that cell to compute the total fish in that connected component.
  4. Update max_fish if the total fish from the current component is greater than the previous maximum.
  5. After scanning the entire grid, return max_fish.

Why it works: Each water cell belongs to exactly one connected component. DFS ensures that we sum all fish in a component while marking cells as visited to avoid double-counting. Therefore, max_fish correctly captures the maximum obtainable fish.

Python Solution

from typing import List

class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        max_fish = 0

        def dfs(r: int, c: int) -> int:
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
                return 0
            fish = grid[r][c]
            grid[r][c] = 0  # mark visited
            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                fish += dfs(r + dr, c + dc)
            return fish

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] > 0:
                    max_fish = max(max_fish, dfs(r, c))

        return max_fish

This Python solution iterates through each cell, starts a DFS from unvisited water cells, sums all fish in the connected component, and updates the maximum. Marking visited cells as 0 prevents revisiting and ensures correctness.

Go Solution

func findMaxFish(grid [][]int) int {
    rows, cols := len(grid), len(grid[0])
    maxFish := 0

    var dfs func(r, c int) int
    dfs = func(r, c int) int {
        if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 0 {
            return 0
        }
        fish := grid[r][c]
        grid[r][c] = 0 // mark visited
        directions := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}
        for _, d := range directions {
            fish += dfs(r + d[0], c + d[1])
        }
        return fish
    }

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] > 0 {
                total := dfs(r, c)
                if total > maxFish {
                    maxFish = total
                }
            }
        }
    }

    return maxFish
}

The Go version mirrors the Python approach, using a recursive closure for DFS. Differences include explicit array-based direction handling and updating maxFish with a comparison instead of using max.

Worked Examples

Example 1: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]

Starting at (1,3):

Cell Visited Fish Collected Running Total
(1,3) 3 3
(2,3) 4 7

Maximum fish in any connected component is 7.

Example 2: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]

Starting at (0,0):

Cell Visited Fish Collected Running Total
(0,0) 1 1

Starting at (3,3):

Cell Visited Fish Collected Running Total
(3,3) 1 1

Maximum fish is 1.

Complexity Analysis

Measure Complexity Explanation
Time O(m*n) Each cell is visited at most once during DFS
Space O(m*n) Recursive call stack in worst case fills entire grid

Since m, n <= 10, the algorithm efficiently explores all connected water components without unnecessary recomputation.

Test Cases

# Provided examples
assert Solution().findMaxFish([[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]) == 7  # connected water component
assert Solution().findMaxFish([[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]) == 1  # isolated water cells

# Edge and additional cases
assert Solution().findMaxFish([[0]]) == 0  # single land cell
assert Solution().findMaxFish([[5]]) == 5  # single water cell
assert Solution().findMaxFish([[0,0],[0,0]]) == 0  # all land
assert Solution().findMaxFish([[1,1],[1,1]]) == 4  # all water
assert Solution().findMaxFish([[0,1,0],[1,1,1],[0,1,0]]) == 5  # plus shape water
Test Why
Example 1 Tests connected component with multiple fish
Example 2 Tests isolated water cells
[[0]] Single land cell
[[5]] Single water cell
[[0,0],[0,0]] All land grid
[[1,1],[1,1]] All water grid
[[0,1,0],[1,1,1],[0,1,0]] Non-trivial connected shape

Edge Cases

All land: A grid with no water should return 0. This is handled by checking grid[r][c] > 0 before DFS.

Single water cell: The algorithm must correctly handle a single water cell without neighbors. DFS will return the fish at that cell.

Disconnected water components: Multiple disconnected water clusters must be independently evaluated to ensure the maximum is correctly identified. DFS marks visited cells as 0, so each component is counted only once.

Non-rectangular clusters: The solution correctly handles irregular shapes because DFS explores all four directions recursively. This ensures that any arbitrarily shaped water cluster is fully traversed.