Maximum Number of Fish in a Grid — Medium Problem & Solution

A grid represents a pond: grid[i][j] == 0 is a land cell, and a positive value is a water cell holding that many fish.

Difficulty: Medium
Topics: Arrays, Matrix, Breadth-First Search, Depth-First Search, Union Find
Asked at: Amazon, Microsoft, Paytm
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A grid represents a pond: grid[i][j] == 0 is a land cell, and a positive value is a water cell holding that many fish.

A fisher may start at any water cell, catch all its fish, and then move to an adjacent water cell (up, down, left or right), repeating as long as they like. Return the largest total catch possible, or 0 if there is no water.

Example 1

Input: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
Output: 7
Explanation: Start at `(1,3)` with 3 fish and move down to `(2,3)` with 4.

Example 2

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
Output: 1
Explanation: Two isolated cells of one fish each.

Example 3

Input: grid = [[0,0],[0,0]]
Output: 0

Constraints

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

How to solve Maximum Number of Fish in a Grid

Moving between adjacent water cells means the fisher can sweep an entire connected component of water. So the problem reduces to summing each component and taking the largest.

Approach

Scan for an unvisited positive cell.
Flood-fill from it with a stack or queue, summing values and marking cells visited.
Track the largest sum seen.

Why it works

Since moves are reversible and unlimited, everything reachable from the start is exactly its connected component, and the fisher can tour all of it. Nothing outside is reachable, so the best catch is the maximum component sum — no ordering or path optimisation is involved at all.

Complexity

Time — O(m · n)
Space — O(m · n)

Pitfalls

Cells with 0 are land and break connectivity; they are not empty water.
Mark visited on push, not on pop, or a cell is counted twice.
A grid of all land answers 0.

Reference solution

Python

from typing import List

def findMaxFish(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    seen = [[False] * n for _ in range(m)]
    best = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 0 or seen[i][j]:
                continue
            total = 0
            stack = [(i, j)]
            seen[i][j] = True
            while stack:
                r, c = stack.pop()
                total += grid[r][c]
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] > 0 and not seen[nr][nc]:
                        seen[nr][nc] = True
                        stack.append((nr, nc))
            best = max(best, total)
    return best

JavaScript

var findMaxFish = function(grid) {
    var m = grid.length, n = grid[0].length, i, j;
    var seen = [];
    for (i = 0; i < m; i++) {
        var row = [];
        for (j = 0; j < n; j++) row.push(false);
        seen.push(row);
    }
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    var best = 0;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (grid[i][j] === 0 || seen[i][j]) continue;
            var sum = 0;
            var stack = [i * n + j];
            seen[i][j] = true;
            while (stack.length > 0) {
                var cur = stack.pop();
                var r = Math.floor(cur / n), c = cur % n;
                sum += grid[r][c];
                for (var d = 0; d < 4; d++) {
                    var nr = r + dr[d], nc = c + dc[d];
                    if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                    if (grid[nr][nc] === 0 || seen[nr][nc]) continue;
                    seen[nr][nc] = true;
                    stack.push(nr * n + nc);
                }
            }
            if (sum > best) best = sum;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue