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.
For example:
grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
Output: 7 because The fisher can start at cell (1,3) and collect 3 fish, then move to cell (2,3) and collect 4 fish.
As another example:
grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
Output: 1 because The fisher can start at cells (0,0) or (3,3) and collect a single fish. What is the most efficient way to solve this?
Solution
Maximum Number of Fish in a Grid
Naive Approach (Brute Force)
The most straightforward approach is to start from each water cell (cell with a value greater than 0) and explore all possible paths to adjacent water cells using Depth-First Search (DFS) or Breadth-First Search (BFS). For each starting cell, we calculate the total number of fish we can catch and then return the maximum among all these values.
- Iterate through each cell in the grid.
- If a cell is water (grid[r][c] > 0), start a DFS or BFS from that cell.
- During DFS/BFS:
- Keep track of visited cells to avoid cycles.
- Sum the fish in each visited cell.
- Maintain a maximum fish count seen so far.
- Return the maximum fish count.
Optimal Approach (DFS)
A more efficient approach still involves using DFS, but we can avoid redundant calculations. The core idea remains the same: traverse connected water cells to calculate the total number of fish.
- Iterate through each cell in the grid.
- If a cell is water and unvisited (grid[r][c] > 0), start a DFS from that cell.
- During DFS:
- Mark the current cell as visited to prevent cycles.
- Add the fish in the current cell to the current sum.
- Recursively call DFS on adjacent water cells.
- Maintain a maximum fish count seen so far.
- Return the maximum fish count.
Code (Optimal Approach)
def max_fish(grid):
m, n = len(grid), len(grid[0])
visited = set()
max_fishes = 0
def dfs(r, c):
if (r, c) in visited or r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0:
return 0
visited.add((r, c))
fishes = grid[r][c]
fishes += dfs(r + 1, c)
fishes += dfs(r - 1, c)
fishes += dfs(r, c + 1)
fishes += dfs(r, c - 1)
return fishes
for r in range(m):
for c in range(n):
if grid[r][c] > 0 and (r, c) not in visited:
max_fishes = max(max_fishes, dfs(r, c))
return max_fishes
# Example usage
grid = [[0, 2, 1, 0], [4, 0, 0, 3], [1, 0, 0, 4], [0, 3, 2, 0]]
print(max_fish(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 traversal.
- Space Complexity: O(m * n) in the worst case, due to the
visitedset which can contain all the cells of the grid, and the recursion stack depth in the DFS call. In the best case (no connected water) O(1).
Edge Cases
- Empty grid: If the grid is empty (m = 0 or n = 0), return 0.
- No water cells: If there are no water cells (all grid values are 0), return 0.
- Single water cell: If there's only one water cell, return its value.
- Grid with only land cells and one water cell: The algorithm should correctly identify and return the value of the single water cell.
- Disconnected water cells: The algorithm handles this correctly by starting a new DFS from each unvisited water cell.
