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.
This approach involves treating the grid as a graph and using depth-first search to explore each connected component of water cells. The goal is to aggregate the number of fish in each connected component and return the maximum number encountered. We start from each unvisited water cell and attempt to explore the maximum number of fish that can be collected from that starting point using DFS.
The function dfs is a recursive implementation of depth-first search, used to explore all reachable water cells starting from a given cell. It aggregates the fish count for a connected component. The main function maxFish iterates through all cells, starting a DFS search whenever an unvisited water cell is encountered. The maximum fish count from all searches is tracked and returned as the result.
Time Complexity: O(m*n), where m and n are the dimensions of the grid. Each cell is visited once.
Space Complexity: O(m*n), to store the visited state of each cell.
This alternative approach uses breadth-first search to traverse each component of water cells in the grid. Instead of exploring depth-first, it explores all neighbor cells at the present "depth" before moving deeper. The total number of fish for each component is counted, with the goal of finding the maximum possible collection.
This C code uses BFS via a queue to explore each connected group of water cells starting from an unvisited starting cell. It maintains a queue to store cells to be visited, and each cell is processed in BFS manner. Every neighbor is explored and added to the queue if it's not visited, aggregating the fish count for that component.
Time Complexity: O(m*n) given the fixed maximum grid size allowing linear traversal.
Space Complexity: O(m*n), to handle the visitation status and queue space.
According to the problem description, we only need to find the number of fish in each connected water area and then take the maximum value. Therefore, we can use the depth-first search method to solve this problem.
We define a function dfs(i, j), which indicates the maximum number of fish that can be caught starting from the cell in the i-th row and the j-th column. The execution logic of the function dfs(i, j) is as follows:
We use a variable cnt to record the number of fish in the current cell, and then set the number of fish in the current cell to 0, indicating that it has been fished. Then we traverse the four directions of the current cell, if the cell (x, y) in a certain direction is in the grid and is a water cell, then we recursively call the dfs(x, y) function and add the return value to cnt. Finally, return cnt.
In the main function, we traverse all the cells (i, j). If the current cell is a water cell, we call the dfs(i, j) function, take the maximum value of the return value as the answer, and return it.
The time complexity is O(m times n), and the space complexity is O(m times n). where m and n are the number of rows and columns of the grid graph respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) | Time Complexity: O(m*n), where m and n are the dimensions of the grid. Each cell is visited once. Space Complexity: O(m*n), to store the visited state of each cell. |
| Breadth-First Search (BFS) | Time Complexity: O(m*n) given the fixed maximum grid size allowing linear traversal. Space Complexity: O(m*n), to handle the visitation status and queue space. |
| DFS | — |
| 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. |
Maximum Number of Fish in a Grid - Leetcode 2658 - Python • NeetCodeIO • 6,941 views views
Watch 9 more video solutions →Practice Maximum Number of Fish in a Grid with our built-in code editor and test cases.
Practice on FleetCode