2658. Maximum Number of Fish in a Grid - Detailed Explanation

Problem Statement

You are given an m x n grid where each cell contains a non-negative integer representing the number of fish in that cell. A cell with a value of 0 means there are no fish in that cell. Two cells are considered connected if they are adjacent horizontally or vertically. Your task is to find the maximum total number of fish that can be collected from any connected group of cells.

Key Points:

• Cells with a value of 0 cannot be part of any connected group (or they contribute 0).
• You can only move in four directions: up, down, left, or right.
• Return the maximum sum of fish in any connected component of the grid.
• If there are no cells with fish (i.e. all cells are 0), return 0.

Example 1

• Input:

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

• Output:
  7
• Explanation:
  There are several connected groups:
  • Group A: Cells (0,1) and (0,2) → Sum = 2 + 1 = 3.
  • Group B: Cells (1,0), (2,0), and (2,1) → Sum = 4 + 1 + 2 = 7.
  • Group C: Cells (1,3) and (2,3) → Sum = 3 + 1 = 4.
    The maximum number of fish that can be collected is from Group B, which is 7.

Example 2

• Input:

  grid = [
    [0, 0, 0],
    [0, 0, 0]
  ]
  

• Output:
  0
• Explanation:
  There are no fish in any cell, so the result is 0.

Hints and Intuition

• Hint 1:
  Since the problem is asking for the maximum sum from any connected component, think about how you can use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore connected regions in a grid.

• Hint 2:
  For each cell that contains fish (i.e. has a positive value) and has not yet been visited, start a DFS/BFS to compute the total sum of fish in that connected component. Track the maximum sum among all connected components.

• Hint 3:
  Use a "visited" data structure (or modify the grid in place) to ensure that you do not count the same cell more than once.

Detailed Approach

A. Using Depth-First Search (DFS)

1. Iterate through the Grid:
   For each cell (i, j) that has a value greater than 0 and is not visited, initiate a DFS.

2. Perform DFS:

   • Mark the cell as visited.
   • Add its fish count to the current component’s sum.
   • Explore all four adjacent cells (up, down, left, right) that are within bounds and have a non-zero value.
   • Continue the DFS recursively for each eligible neighbor.

3. Update Maximum Sum:
   After completing the DFS for a connected component, update the maximum fish sum if the current component’s sum is greater.

4. Return the Result:
   Once all cells have been processed, return the maximum sum obtained.

B. Alternative: Using Breadth-First Search (BFS)

• You can also use BFS starting from each unvisited cell with fish. The logic is similar: use a queue to explore neighbors and sum the fish values for each connected component.

Step-by-Step Walkthrough with Visual Example

Consider Example 1:

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

1. Start at (0,1):

   • Value = 2. Mark as visited.
   • Check right (0,2) → Value = 1 (valid).
   • DFS from (0,2) adds 1.
   • Component sum becomes 2 + 1 = 3.

2. Next unvisited cell with fish at (1,0):

   • Value = 4. Mark as visited.
   • Check downward (2,0) → Value = 1.
   • From (2,0), check right (2,1) → Value = 2.
   • Component sum becomes 4 + 1 + 2 = 7.

3. Next, cell (1,3):

   • Value = 3. Mark as visited.
   • Check downward (2,3) → Value = 1.
   • Component sum becomes 3 + 1 = 4.

4. Maximum sum among the groups is 7.

Code Implementation

Python Implementation