Maximum Number of Fish in a Grid

Tested Python solution for LeetCode 2658 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 2658, Medium. Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 18 parametrized pytest cases, and a playground notebook:

lcpy gen -n 2658   # by problem number
lcpy gen -s maximum_number_of_fish_in_a_grid   # by problem name

​

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.

​

Examples

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.

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

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import deque


class Solution:
    # Time: O(m * n)
    # Space: O(m * n)
    def find_max_fish(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        seen = [[False] * cols for _ in range(rows)]
        best = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] > 0 and not seen[r][c]:
                    seen[r][c] = True
                    queue = deque([(r, c)])
                    total = 0
                    while queue:
                        cr, cc = queue.popleft()
                        total += grid[cr][cc]
                        for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
                            if (
                                0 <= nr < rows
                                and 0 <= nc < cols
                                and grid[nr][nc] > 0
                                and not seen[nr][nc]
                            ):
                                seen[nr][nc] = True
                                queue.append((nr, nc))
                    best = max(best, total)
        return best

​

Complexity

Time	Space
O(m * n)	O(m * n)

​

Tags

NeetCode All.