How do you solve Maximum Number of Fish in a Grid on LeetCode?

Maximum Number of Fish in a Grid (LeetCode #2658) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m * n) time complexity and O(m * n) space complexity. Key insight: Using a visited matrix prevents double counting of fish in connected components.

What is the time complexity of Maximum Number of Fish in a Grid?

The optimal solution for Maximum Number of Fish in a Grid runs in O(m * n) time and uses O(m * n) space. This complexity arises because we visit each cell exactly once, and the space complexity is due to the visited matrix.

What is the brute force solution for Maximum Number of Fish in a Grid?

The brute force approach for Maximum Number of Fish in a Grid is Brute Force, with O(m * n * (m + n)) time complexity and O(1) space complexity. We can start from each water cell and use Depth-First Search (DFS) to explore all reachable water cells, summing the fish as we go. This method ensures we check every possible starting point. The optimal Optimal Solution approach improves this to O(m * n).

What are the interview tips for Maximum Number of Fish in a Grid?

Always clarify the problem and constraints before jumping into coding. Discuss your thought process and approach with the interviewer. Consider edge cases, such as grids with no water cells.

What are common mistakes when solving Maximum Number of Fish in a Grid?

Forgetting to mark cells as visited, leading to infinite loops. Not checking for boundary conditions when exploring adjacent cells.

#2658

Maximum Number of Fish in a Grid

Medium

ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrixDepth-First Search (DFS)Graph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(m * n * (m + n))	O(m * n)
Space	O(1)	O(m * n)

💡

Intuition

Time O(m * n)Space O(m * n)

Instead of starting from every water cell, we can use a visited matrix to avoid counting the same fish multiple times. This allows us to efficiently explore connected components of water cells.

⚙️

Algorithm

4 steps

1Step 1: Create a visited matrix to track which cells have been counted.
2Step 2: Iterate through each cell in the grid.
3Step 3: For each unvisited water cell, perform DFS to collect fish and mark cells as visited.
4Step 4: Keep track of the maximum number of fish collected from any connected component.

solution.py23 lines

1# Full working Python code
2
3def maxFish(grid):
4    m, n = len(grid), len(grid[0])
5    visited = [[False] * n for _ in range(m)]
6
7    def dfs(r, c):
8        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0 or visited[r][c]:
9            return 0
10        visited[r][c] = True
11        fish = grid[r][c]
12        total = fish
13        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
14            total += dfs(r + dr, c + dc)
15        return total
16
17    max_fish = 0
18    for r in range(m):
19        for c in range(n):
20            if grid[r][c] > 0 and not visited[r][c]:
21                max_fish = max(max_fish, dfs(r, c))
22    return max_fish
23

ℹ

Complexity note: This complexity arises because we visit each cell exactly once, and the space complexity is due to the visited matrix.

1Using a visited matrix prevents double counting of fish in connected components.
2DFS helps explore all reachable water cells efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.