Maximum Number of Fish in a Grid

Maximum Number of Fish in a Grid

What is this problem about?

The Maximum Number of Fish in a Grid coding problem gives you a 2D grid where each cell either contains 0 (water) or a positive number (land with fish). Starting from any land cell, you can move to adjacent land cells (4-directionally) and collect all fish. You want to find the maximum total fish collectible from any single connected land component.

Why is this asked in interviews?

Microsoft, Meta, Amazon, and Google include this problem as a clean BFS/DFS connected component problem with a value-aggregation twist. It tests whether candidates can correctly enumerate connected components in a grid and aggregate values. It is a natural extension of the island-counting problem family, adding the requirement to maximize sum rather than count components.

Algorithmic pattern used

BFS or DFS flood-fill: For each unvisited land cell, run a BFS/DFS to explore the entire connected component, summing all fish values. Mark cells as visited (set to 0 or use a separate visited array). Track the maximum sum seen across all components. Time: O(mn), Space: O(mn) for the visited set or call stack.

Union-Find is also applicable: unite adjacent land cells, track component sums, find the maximum.

Example explanation

Grid:

0  2  1  0
4  0  0  3
1  0  0  4
0  3  2  0

• Component starting at (0,1): cells (0,1)=2, (0,2)=1. Sum=3.
• Component at (1,0): (1,0)=4, (2,0)=1. Sum=5.
• Component at (1,3): (1,3)=3, (2,3)=4. Sum=7.
• Component at (3,1): (3,1)=3, (3,2)=2. Sum=5.
• Maximum = 7.

Common mistakes candidates make

• Not marking cells as visited: Revisiting cells double-counts fish.
• Diagonal movement: Only 4-directional (up/down/left/right) movement is allowed — not diagonal.
• Treating 0 as a land cell: Cells with value 0 are water and cannot be entered or collected from.

Interview preparation tip

For the Array Matrix Union Find Breadth-First Search Depth-First Search interview pattern, this problem is an excellent template for "max value connected component" problems. Implement the DFS version as a recursive helper that returns the sum of the current component, then iterate over all cells calling it on unvisited land cells. Practice this template for grids with islands, connected components, and value aggregation.