Problem Description

You are given a 2D matrix grid of size m x n where each cell (r, c) represents either:

• A land cell if grid[r][c] = 0
• A water cell containing grid[r][c] fish if grid[r][c] > 0

A fisher can start at any water cell and perform these operations any number of times:

• Catch all the fish at the current cell
• Move to any adjacent water cell (up, down, left, or right)

The goal is to find the maximum number of fish the fisher can catch by choosing the optimal starting cell. If no water cells exist in the grid, return 0.

An adjacent cell of (r, c) is one of the four cells: (r-1, c), (r+1, c), (r, c-1), or (r, c+1), provided they exist within the grid boundaries.

The key insight is that once the fisher starts at a water cell, they can traverse through all connected water cells (forming a connected component) and collect all the fish in that region. The answer is the maximum sum of fish across all such connected water regions in the grid.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a 2D grid where water cells are connected to adjacent water cells. We can think of each water cell as a node, and adjacency relationships (up, down, left, right) as edges. The fisher can move between connected water cells, making this a graph traversal problem.

Is it a tree?

• No: The water cells form connected components that may contain cycles (e.g., a 2x2 block of water cells). Multiple water cells can be connected in various ways, not following a tree structure.

Is the problem related to directed acyclic graphs?

• No: The movement between water cells is bidirectional (the fisher can move back and forth between adjacent water cells), and the graph is undirected. Additionally, cycles can exist.

Is the problem related to shortest paths?

• No: We're not looking for the shortest path between cells. Instead, we want to collect all fish in a connected component of water cells.

Does the problem involve connectivity?

• Yes: The core of the problem is finding connected components of water cells. The fisher can traverse through all connected water cells starting from any water cell, collecting all fish in that connected region.

Does the problem have small constraints?

• Yes: While not explicitly stated, grid problems typically have manageable constraints that allow for DFS/BFS traversal without timeout issues.

DFS/backtracking?

• Yes: DFS is perfect for exploring all cells in a connected component. We start from a water cell and recursively visit all adjacent water cells, collecting fish along the way.

Conclusion: The flowchart suggests using DFS to explore connected components of water cells and find the maximum sum of fish across all components.

Intuition

When we look at this problem, we need to understand what happens when the fisher starts at a water cell. Once they begin, they can move freely between adjacent water cells, collecting all the fish along the way. This means if water cells are connected (adjacent to each other), the fisher can collect all fish from that entire connected region in a single journey.

The key insight is that the grid is divided into separate "islands" of water cells. Each island is a connected component where all water cells can be reached from any starting water cell within that island. The fisher must choose one island to fish from, and they will collect all fish from that entire island.

This naturally leads us to think about finding all connected components of water cells in the grid. For each connected component, we need to:

1. Calculate the total number of fish in that component
2. Keep track of the maximum total we've seen

Why DFS works perfectly here? When we start DFS from a water cell, it will naturally explore all reachable water cells (the entire connected component) and can sum up all the fish values along the way. Once we've visited a cell, we mark it as visited (or set it to 0) to avoid counting it again.

The approach becomes clear:

• Try starting from every water cell in the grid
• For each starting point, use DFS to explore the entire connected component and sum up all fish
• Keep track of the maximum sum encountered

Since each water cell belongs to exactly one connected component, and we mark cells as visited after processing, each connected component will be processed exactly once, giving us the correct maximum.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The solution implements a DFS traversal to find all connected components of water cells and calculate their fish totals.

Main Algorithm Structure:

1. DFS Function Implementation: We define a recursive function dfs(i, j) that:

   • Takes the current cell coordinates (i, j) as parameters
   • Records the fish count at the current cell in variable cnt
   • Marks the cell as visited by setting grid[i][j] = 0 (converting it to land)
   • Explores all four adjacent cells recursively

2. Direction Traversal: The code uses pairwise((-1, 0, 1, 0, -1)) to generate direction pairs:

   • This creates pairs: (-1, 0), (0, 1), (1, 0), (0, -1)
   • These represent movements: up, right, down, left
   • For each direction (a, b), we calculate the new position (x, y) = (i + a, j + b)

3. Boundary and Water Cell Check: Before recursing to an adjacent cell, we verify:

   • The cell is within grid boundaries: 0 <= x < m and 0 <= y < n
   • The cell is a water cell: grid[x][y] > 0
   • If both conditions are met, we recursively call dfs(x, y) and add its return value to cnt

4. Main Loop Processing:

   • Initialize ans = 0 to track the maximum fish count
   • Iterate through every cell (i, j) in the grid
   • If grid[i][j] > 0 (water cell), call dfs(i, j) to explore its connected component
   • Update ans with the maximum value between current ans and the DFS result

Key Implementation Details:

• In-place Marking: Instead of using a separate visited array, we modify the grid directly by setting visited cells to 0. This saves space but modifies the input.

• Component Isolation: Once a connected component is fully explored via DFS, all its cells are marked as 0, ensuring we don't count the same component multiple times.

• Return Value: Each dfs call returns the total fish count for the connected component starting from that cell.

The time complexity is O(m × n) where each cell is visited at most once, and the space complexity is O(m × n) in the worst case for the recursion stack when all cells form one connected component.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3×4 grid:

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

Where 0 represents land and positive numbers represent water cells with fish.

Step 1: Identify Connected Water Components

Looking at the grid, we can identify three separate water regions:

• Component 1 (top): cells (0,1) with 2 fish and (0,2) with 1 fish
• Component 2 (left): cells (1,0) with 4 fish and (2,0) with 1 fish
• Component 3 (right): cells (1,3) with 3 fish and (2,3) with 4 fish

Step 2: Process Each Cell

Starting from (0,0): It's land (value = 0), skip.

At (0,1): Water cell with 2 fish! Start DFS:

• Current cell (0,1): collect 2 fish, mark as 0
• Check neighbors:
  • Up (-1,1): out of bounds
  • Right (0,2): water cell with 1 fish, recurse
    • At (0,2): collect 1 fish, mark as 0
    • Check its neighbors: all are land or out of bounds
    • Return 1
  • Down (1,1): land (0), skip
  • Left (0,0): land (0), skip
• Total for this component: 2 + 1 = 3

Update ans = max(0, 3) = 3

Grid after first DFS:

[[0, 0, 0, 0],
 [4, 0, 0, 3],
 [1, 0, 0, 4]]

At (0,2): Already visited (now 0), skip.

Continue scanning... At (1,0): Water cell with 4 fish! Start DFS:

• Current cell (1,0): collect 4 fish, mark as 0
• Check neighbors, find (2,0) with 1 fish
• At (2,0): collect 1 fish, mark as 0
• Total for this component: 4 + 1 = 5

Update ans = max(3, 5) = 5

Continue scanning... At (1,3): Water cell with 3 fish! Start DFS:

• Current cell (1,3): collect 3 fish, mark as 0
• Check neighbors, find (2,3) with 4 fish
• At (2,3): collect 4 fish, mark as 0
• Total for this component: 3 + 4 = 7

Update ans = max(5, 7) = 7

Step 3: Final Result

After processing all cells, the maximum fish caught is 7 (from the rightmost water component).

The algorithm correctly identifies that starting from either (1,3) or (2,3) allows the fisher to collect all 7 fish from that connected water region, which is the optimal choice.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm uses DFS to traverse connected components in the grid. In the worst case, every cell in the grid is visited exactly once. The main loop iterates through all m × n cells, and for each cell that contains fish (non-zero value), it initiates a DFS. During the DFS traversal, each cell is visited at most once because once visited, it's marked as 0 (effectively marking it as visited). Therefore, the total time complexity is O(m × n).

Space Complexity: O(m × n)

The space complexity is dominated by the recursion stack depth in the DFS. In the worst case, when all cells form a single connected component (all cells contain fish and are connected), the DFS could go as deep as m × n levels. This happens when the connected component forms a long path through the grid. Additionally, the pairwise function creates temporary tuples for direction pairs, but this is O(1) space. Therefore, the overall space complexity is O(m × n) due to the recursion stack.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Input Grid

The current solution modifies the input grid by setting visited cells to 0. This is destructive and may not be acceptable in scenarios where:

• The input grid needs to be preserved for other operations
• The problem explicitly states not to modify the input
• You're working in a production environment where side effects should be avoided

Solution: Create a separate visited tracking mechanism:

def findMaxFish(self, grid: List[List[int]]) -> int:
    def dfs(row: int, col: int, visited: set) -> int:
        if (row, col) in visited:
            return 0
      
        visited.add((row, col))
        fish_count = grid[row][col]
      
        for delta_row, delta_col in pairwise((-1, 0, 1, 0, -1)):
            next_row = row + delta_row
            next_col = col + delta_col
          
            if (0 <= next_row < rows and 
                0 <= next_col < cols and 
                grid[next_row][next_col] > 0 and
                (next_row, next_col) not in visited):
                fish_count += dfs(next_row, next_col, visited)
      
        return fish_count
  
    rows = len(grid)
    cols = len(grid[0])
    max_fish = 0
    global_visited = set()
  
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] > 0 and (i, j) not in global_visited:
                component_visited = set()
                max_fish = max(max_fish, dfs(i, j, component_visited))
                global_visited.update(component_visited)
  
    return max_fish

2. Stack Overflow for Large Connected Components

The recursive DFS approach can cause stack overflow when dealing with very large connected components (e.g., a grid where all cells are water).

Solution: Use iterative DFS with an explicit stack:

def findMaxFish(self, grid: List[List[int]]) -> int:
    def dfs_iterative(start_row: int, start_col: int) -> int:
        stack = [(start_row, start_col)]
        fish_count = 0
      
        while stack:
            row, col = stack.pop()
          
            if row < 0 or row >= rows or col < 0 or col >= cols:
                continue
            if grid[row][col] <= 0:
                continue
              
            fish_count += grid[row][col]
            grid[row][col] = 0
          
            # Add all adjacent cells to stack
            stack.extend([
                (row - 1, col),
                (row + 1, col),
                (row, col - 1),
                (row, col + 1)
            ])
      
        return fish_count
  
    rows = len(grid)
    cols = len(grid[0])
    max_fish = 0
  
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] > 0:
                max_fish = max(max_fish, dfs_iterative(i, j))
  
    return max_fish

3. Missing Import for pairwise

The pairwise function is only available in Python 3.10+. Code will fail on earlier versions.

Solution: Implement direction traversal explicitly:

def findMaxFish(self, grid: List[List[int]]) -> int:
    def dfs(row: int, col: int) -> int:
        fish_count = grid[row][col]
        grid[row][col] = 0
      
        # Explicit direction vectors: up, right, down, left
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
      
        for delta_row, delta_col in directions:
            next_row = row + delta_row
            next_col = col + delta_col
          
            if (0 <= next_row < rows and 
                0 <= next_col < cols and 
                grid[next_row][next_col] > 0):
                fish_count += dfs(next_row, next_col)
      
        return fish_count
  
    # Rest of the code remains the same