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.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Matrix, Breadth-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.lengthn == grid[i].length1 <= m, n <= 100 <= grid[i][j] <= 10
Hints for Maximum Number of Fish in a Grid
Hint 1
The fisher can reach every water cell connected to the start, so the catch is a whole connected region.
Hint 2
Find the connected components of the positive cells.
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
- 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
0are 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 bestJava
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)