Maximum Number of Fish in a Grid
MedPrompt
You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:
- A land cell if
grid[r][c] = 0, or - A water cell containing
grid[r][c]fish, ifgrid[r][c] > 0.
A fisher can start at any water cell (r, c) and can do the following operations any number of times:
- Catch all the fish at cell
(r, c), or - Move to any adjacent water cell.
Return 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:
(1,3)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] <= 10
Approaches
2 approaches with complexity analysis and trade-offs.
This approach iterates through every cell in the grid. If a cell contains water (i.e., has fish), it is considered a potential starting point. For each such potential starting point, a new traversal (like Depth-First Search or DFS) is initiated to find all reachable water cells and sum up the fish. This process is repeated for every water cell, and the maximum sum found across all starting points is returned.
Algorithm
- Initialize
maxFish = 0. - Iterate through each cell
(r, c)from(0, 0)to(m-1, n-1). - If
grid[r][c] > 0:- Create a new
boolean[][] visitedarray of sizem x nand initialize all its values tofalse. - Call a traversal function (e.g., DFS) starting from
(r, c)to calculate the total fish in the connected component. Let this becurrentFish. - The DFS function works as follows:
- Base case: If the cell is out of bounds, is land, or has been visited, return 0.
- Mark the current cell as visited.
- Initialize a local sum with the fish in the current cell.
- Recursively call DFS for all four adjacent cells (up, down, left, right) and add the results to the local sum.
- Return the local sum.
- Update
maxFish = max(maxFish, currentFish).
- Create a new
- After the loops complete, return
maxFish.
Walkthrough
The main idea is to test every possible starting water cell and calculate the total fish that can be caught from that start.
We initialize a variable maxFish to 0. We then loop through each cell (r, c) of the m x n grid. If grid[r][c] > 0, it's a water cell and a valid starting point. From this cell (r, c), we start a traversal to find the total fish in its connected component. To do this, we must keep track of visited cells for this specific traversal to avoid infinite loops and recounting fish. So, we create a new boolean[][] visited array for each call from the main loop.
A recursive DFS function is a good fit here. The DFS function would take the current cell's coordinates, the grid, and the visited array. It would add the fish from the current cell, mark it as visited, and then recursively call itself for all adjacent, unvisited water cells. The sum returned by the traversal from (r, c) is compared with maxFish, and maxFish is updated if the new sum is larger. After checking all cells in the grid, maxFish will hold the maximum possible catch.
class Solution { public int findMaxFish(int[][] grid) { int maxFish = 0; int m = grid.length; int n = grid[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] > 0) { // For each water cell, start a new traversal boolean[][] visited = new boolean[m][n]; int currentFish = dfs(i, j, grid, visited); maxFish = Math.max(maxFish, currentFish); } } } return maxFish; } private int dfs(int r, int c, int[][] grid, boolean[][] visited) { int m = grid.length; int n = grid[0].length; // Check bounds and if the cell is valid (water and not visited) if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) { return 0; } // Mark as visited for this traversal visited[r][c] = true; int fishCount = grid[r][c]; // Explore neighbors fishCount += dfs(r + 1, c, grid, visited); fishCount += dfs(r - 1, c, grid, visited); fishCount += dfs(r, c + 1, grid, visited); fishCount += dfs(r, c - 1, grid, visited); return fishCount; }}Complexity
Time
O(m^2 * n^2), where `m` is the number of rows and `n` is the number of columns. The outer loops iterate through all `m * n` cells. For each water cell, we initiate a DFS traversal. In the worst case (a grid full of water), the DFS traversal visits `m * n` cells. This results in a total complexity of `O((m * n) * (m * n))`.
Space
O(m * n). For each traversal started from the main loop, a new `visited` array of size `m x n` is created. Additionally, the recursion stack for DFS can go up to `m * n` deep in the worst case (a snake-like path through the grid).
Trade-offs
Pros
Simple to conceptualize: for every possible start, find the total catch.
Correctly solves the problem.
Cons
Highly inefficient due to redundant computations. The same connected component of water is traversed and its fish summed up multiple times, once for each cell within that component.
Solutions
Solution
class Solution {private int[][] grid;private int m;private int n;public int findMaxFish(int[][] grid) { m = grid.length; n = grid[0].length; this.grid = grid; int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] > 0) { ans = Math.max(ans, dfs(i, j)); } } } return ans; }private int dfs(int i, int j) { int cnt = grid[i][j]; grid[i][j] = 0; int[] dirs = {-1, 0, 1, 0, -1}; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) { cnt += dfs(x, y); } } return cnt; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.