MediumNo. 2658
Maximum Number of Fish in a Grid — LeetCode 2658 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Array, Matrix
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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, 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: Catch all the fish at cell (r, c), or Move to any adjacent water cell.
Example
- 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.
Python solution
class Solution:
def findMaxFish(self, grid: List[List[int]]) -> int:
def dfs(i: int, j: int) -> int:
cnt = grid[i][j]
grid[i][j] = 0
for a, b in pairwise((-1, 0, 1, 0, -1)):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y]:
cnt += dfs(x, y)
return cnt
m, n = len(grid), len(grid[0])
ans = 0
for i in range(m):
for j in range(n):
if grid[i][j]:
ans = max(ans, dfs(i, j))
return ansComplexity
- Time
- O(m × n)
- Space · auxiliary
- O(m × n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2658. Maximum Number of Fish in a Grid is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0130 | Surrounded Regions | Medium |
| 0200 | Number of Islands | Medium |
| 0695 | Max Area of Island | Medium |
| 0827 | Making A Large Island | Hard |
| 1020 | Number of Enclaves | Medium |
| 1254 | Number of Closed Islands | Medium |
Frequently asked questions
- How hard is LeetCode 2658. Maximum Number of Fish in a Grid?
LeetCode 2658. Maximum Number of Fish in a Grid is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2658. Maximum Number of Fish in a Grid?
The Python solution on this page runs in O(m × n).
- What is the space complexity of LeetCode 2658. Maximum Number of Fish in a Grid?
The Python solution on this page uses O(m × n) auxiliary space.
- What topics does LeetCode 2658. Maximum Number of Fish in a Grid cover?
LeetCode 2658. Maximum Number of Fish in a Grid is tagged Depth-First Search, Breadth-First Search, Union Find, Array and Matrix on LeetCode.