Maximum Number of Fish in a Grid
Medium
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:
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:
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.
Can you provide an efficient algorithm to solve this problem, along with its time and space complexity analysis? Also, discuss any edge cases that need to be considered.
Solution
Maximum Fish Problem
Naive Approach
A brute-force approach would involve starting at each water cell (grid[r][c] > 0) and exploring all possible paths to adjacent water cells using a depth-first search (DFS) or breadth-first search (BFS). We would keep track of the maximum number of fish collected along any path and return that value.
Optimal Approach
A more efficient approach also uses DFS, but it marks visited cells to avoid cycles and redundant computations. For each water cell, we initiate a DFS to explore the connected component of water cells. During the DFS, we accumulate the number of fish in the connected component. We keep track of the maximum number of fish found across all connected components.
Algorithm
- Initialize
max_fishto 0. - Iterate through each cell
(r, c)in the grid. - If
grid[r][c] > 0, start a DFS from that cell:- Mark the cell as visited by setting
grid[r][c] = 0(or using a separate visited array). - Recursively explore adjacent water cells
(r+1, c),(r-1, c),(r, c+1),(r, c-1). Add the fish in each adjacent cell to the current fish count.
- Mark the cell as visited by setting
- Update
max_fishwith the maximum fish count found so far. - Return
max_fish.
Code (Python)
def max_fish_catch(grid):
m, n = len(grid), len(grid[0])
def dfs(r, c):
if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0:
return 0
fish = grid[r][c]
grid[r][c] = 0 # Mark as visited
fish += dfs(r + 1, c)
fish += dfs(r - 1, c)
fish += dfs(r, c + 1)
fish += dfs(r, c - 1)
return fish
max_fish = 0
for r in range(m):
for c in range(n):
if grid[r][c] > 0:
max_fish = max(max_fish, dfs(r, c))
return max_fish
# Example usage:
grid = [[0, 2, 1, 0], [4, 0, 0, 3], [1, 0, 0, 4], [0, 3, 2, 0]]
print(max_fish_catch(grid)) # Output: 7
Big O Analysis
- Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid. Each cell is visited at most once during the DFS.
- Space Complexity: O(m * n) in the worst case due to the recursion depth of the DFS. In the worst case, all cells are water cells, and the DFS stack can grow to the size of the grid.
Edge Cases
- Empty grid: Return 0.
- No water cells: Return 0.
- Grid with only one water cell: Return the fish count of that cell.
- Grid with disconnected water cells: The algorithm correctly finds the maximum fish catch among all disconnected components.
Example
Consider the grid:
[[0, 2, 1, 0],
[4, 0, 0, 3],
[1, 0, 0, 4],
[0, 3, 2, 0]]
The algorithm will:
- Start at (0, 1), find a component of size 2 + 1 = 3
- Start at (1, 0), find a component of size 4 + 1 = 5
- Start at (1, 3), find a component of size 3 + 4 + 3 + 2 = 12. It is important to note that the
gridvalues are set to 0 as the algorithm progresses and avoids revisiting the same grid.
The maximum fish caught will be 7 (3+4).
