You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:
grid[r][c] = 0, orgrid[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:
(r, c), orReturn 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.
Example 1:
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.
Example 2:
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.lengthn == grid[i].length1 <= m, n <= 100 <= grid[i][j] <= 10In #2658 Maximum Number of Fish in a Grid, the grid represents water cells containing fish and land cells with zero fish. The goal is to find the maximum total fish that can be collected from a connected group of water cells.
A common strategy is to treat the grid as a graph and explore connected components. Using Depth-First Search (DFS) or Breadth-First Search (BFS), start from any cell containing fish and traverse all adjacent water cells (up, down, left, right). During traversal, accumulate the fish count and mark cells as visited to avoid revisiting them.
Each traversal effectively computes the total fish in one connected component. By repeating this for all unvisited water cells and tracking the maximum sum, you can determine the best region to fish from. Alternatively, a Union-Find structure can group connected water cells and maintain aggregated fish counts.
This approach processes each cell at most once, resulting in efficient performance for large grids.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS / BFS Traversal | O(m × n) | O(m × n) |
| Union-Find (Disjoint Set) | O(m × n α(m × n)) | O(m × n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Run DFS from each non-zero cell.
Each time you pick a cell to start from, add up the number of fish contained in the cells you visit.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Each cell can be considered a node and adjacent water cells form edges. Treating the grid as a graph allows us to apply standard traversal algorithms like DFS or BFS to find connected components efficiently.
Yes, similar grid traversal and connected-component problems are common in FAANG-style interviews. They test understanding of graph traversal, matrix handling, and optimization techniques.
Graph traversal techniques like DFS using recursion or BFS using a queue work best for this matrix problem. A Union-Find (Disjoint Set) structure can also be used to group connected water cells and maintain fish totals.
The most common approach is to use DFS or BFS to explore connected components of water cells. While traversing, sum the fish values of all reachable cells and track the maximum total among all components.