Maximum Number of Fish in a Grid

Medium
914.

Maximum Number of Fish in a Grid

Maximum Number of Fish in a Grid is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Microsoft and Paytm interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var findMaxFish = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Fish in a Grid — Problem & Solution

Maximum Number of Fish in a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Number of Fish in a Grid is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Microsoft and Paytm interviews.

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

Hints for Maximum Number of Fish in a Grid

  1. Hint 1

    The fisher can reach every water cell connected to the start, so the catch is a whole connected region.

  2. Hint 2

    Find the connected components of the positive cells.

  3. Hint 3

    The answer is the largest component sum.

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

  1. Scan for an unvisited positive cell.
  2. Flood-fill from it with a stack or queue, summing values and marking cells visited.
  3. 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

Java

public static int findMaxFish(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    boolean[][] seen = new boolean[m][n];
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    int[] stack = new int[m * n];
    int best = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0 || seen[i][j]) continue;
            int sum = 0, top = 0;
            stack[top++] = i * n + j;
            seen[i][j] = true;
            while (top > 0) {
                int cur = stack[--top];
                int r = cur / n, c = cur % n;
                sum += grid[r][c];
                for (int d = 0; d < 4; d++) {
                    int 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[top++] = nr * n + nc;
                }
            }
            best = Math.max(best, sum);
        }
    }
    return best;
}

C++

int findMaxFish(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    vector<vector<char>> seen(m, vector<char>(n, 0));
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    int best = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0 || seen[i][j]) continue;
            int sum = 0;
            vector<int> stack;
            stack.push_back(i * n + j);
            seen[i][j] = 1;
            while (!stack.empty()) {
                int cur = stack.back();
                stack.pop_back();
                int r = cur / n, c = cur % n;
                sum += grid[r][c];
                for (int d = 0; d < 4; d++) {
                    int 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] = 1;
                    stack.push_back(nr * n + nc);
                }
            }
            best = max(best, sum);
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)