Watch 10 video solutions for Maximum Number of Fish in a Grid, a medium level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by NeetCodeIO has 6,941 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 10Problem Overview: You are given a 2D grid where each cell contains some fish. A value of 0 represents land, while positive numbers represent water cells containing fish. Starting from any water cell, you can move up, down, left, or right and collect all fish from that connected region. The task is to compute the maximum total fish you can collect from a single connected component.
Approach 1: Depth-First Search (DFS) Traversal (Time: O(m*n), Space: O(m*n))
This approach treats the grid as a graph where each water cell is a node connected to its four directional neighbors. Iterate through every cell in the matrix. When you encounter a cell with fish (grid[r][c] > 0), start a Depth-First Search to explore the entire connected component. During the DFS, accumulate the fish count and mark cells as visited (commonly by setting them to 0 or tracking them in a visited set). Each DFS call walks through all reachable water cells, ensuring every component is processed exactly once. This approach works well because DFS naturally explores entire regions before returning.
Approach 2: Breadth-First Search (BFS) Traversal (Time: O(m*n), Space: O(m*n))
The BFS solution follows the same connected-component idea but uses a queue instead of recursion. When you find a water cell, push it into a queue and start a Breadth-First Search. Repeatedly pop cells from the queue, add their fish count to the running total, and push valid neighboring cells that contain fish. Mark visited cells immediately to avoid revisiting them. BFS explores the region level by level and guarantees each grid cell is processed once. The logic is almost identical to DFS, but BFS avoids recursion depth issues in very large grids.
Approach 3: Union-Find (Disjoint Set) (Time: O(m*n α(n)), Space: O(m*n))
Another way to model the problem is by grouping adjacent water cells using Union Find. Each cell is treated as a node in a disjoint set. When two neighboring cells contain fish, union their sets and maintain a running sum of fish for each component. After processing the entire matrix, scan the component sums and return the maximum. While slightly more complex to implement, this approach generalizes well to problems that require repeated connectivity queries.
Recommended for interviews: DFS or BFS traversal. Interviewers expect you to recognize the grid as a connected-component problem and apply a graph traversal. DFS is usually the fastest to implement, while BFS is equally optimal. Union-Find demonstrates deeper graph modeling but is rarely necessary unless the problem involves dynamic connectivity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) | O(m*n) | O(m*n) | Most common interview solution. Simple recursive traversal for connected components. |
| Breadth-First Search (BFS) | O(m*n) | O(m*n) | Preferred when avoiding recursion or handling very large grids. |
| Union-Find (Disjoint Set) | O(m*n α(n)) | O(m*n) | Useful when modeling connectivity across multiple queries or dynamic merges. |