#2658

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Maximum Number of Fish in a Grid

Maximize the number of fish that can be caught by performing DFS on an optimal starting point in a grid.

array depth first search breadth first search union find matrix

Problem Statement

You are given a 0-indexed 2D matrix grid of size m x n, where each cell can either be water or contain fish. A fisher can start at any water cell and collect fish by moving to adjacent water cells. The fisher collects all fish in the connected region they start from.

The goal is to determine the maximum number of fish the fisher can catch from any valid starting point. If no water cell exists, return 0. You need to find the optimal starting point that allows the fisher to collect the largest possible number of fish.

Examples

Example 1

Input: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]

Output: 7

The fisher can start at cell (1,3) and collect 3 fish, then move to cell (2,3) and collect 4 fish.

Example 2

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]

Output: 1

The fisher can start at cells (0,0) or (3,3) and collect a single fish.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 10
0 <= grid[i][j] <= 10

Solution Approach

DFS from each non-zero cell

The problem can be solved by running a depth-first search (DFS) from each non-zero water cell. For each valid starting point, traverse the connected water cells and sum the number of fish in the region. Keep track of the maximum number of fish caught from any start.

Tracking visited cells

As you traverse the grid using DFS, mark each visited water cell to avoid counting fish in the same region more than once. This ensures the correctness of the solution and avoids redundant work in the search.

Optimizing DFS for grid traversal

To optimize, perform DFS on each unvisited water cell, and at each DFS step, accumulate the total number of fish from the connected cells. This approach ensures you examine all regions, maximizing the fish caught from the best region.

Complexity Analysis

Metric	Value
Time	O((n \cdot m) \cdot \alpha(n \cdot m))
Space	O(n \cdot m)

The time complexity is O((m * n) * α(m * n)), where m is the number of rows, n is the number of columns, and α is the inverse Ackermann function. The space complexity is O(m * n) due to the space required for the DFS stack and visited cells array.

What Interviewers Usually Probe

Ability to handle DFS-based grid problems.
Experience with depth-first search traversal techniques.
Awareness of common pitfalls when traversing connected components.

Common Pitfalls or Variants

Common pitfalls

Forgetting to mark cells as visited, leading to redundant calculations.
Not handling grid boundaries correctly during DFS traversal.
Misinterpreting the problem as a simple grid search without considering the connected components.

Follow-up variants

Implementing BFS instead of DFS for grid traversal.
Introducing different grid sizes and ensuring efficient traversal.
Handling larger grids with optimized algorithms for performance.

FAQ

How do I approach the Maximum Number of Fish in a Grid problem?

Start by performing DFS from each non-zero water cell, keeping track of the maximum number of fish caught. Make sure to mark visited cells.

What is the time complexity of solving this problem?

The time complexity is O((m * n) * α(m * n)), where m and n are the grid dimensions, and α is the inverse Ackermann function.

Can I use BFS for the Maximum Number of Fish in a Grid problem?

Yes, BFS can be used as an alternative to DFS, especially if you prefer iterative solutions over recursive depth-first search.

How do I ensure the DFS does not revisit cells?

Use a visited array or mark cells in the grid to ensure each cell is only visited once during DFS traversal.

What are the most common pitfalls when solving this problem?

The most common pitfalls include forgetting to mark cells as visited, not properly handling grid boundaries, and misinterpreting the problem's requirements.

terminal

Solution

Solution 1: DFS

According to the problem description, we only need to find the number of fish in each connected water area and then take the maximum value. Therefore, we can use the depth-first search method to solve this problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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 ans

Continue Practicing

#1970 last day where you can still cross #1905 count sub islands #3619 count islands with total value divisible by k