2658. Maximum Number of Fish in a Grid


Problem Description

The problem presents a 2D matrix grid representing a 'fishing grid' where each cell is either land or water. The cells containing water have a non-zero value representing the number of fish present. A cell with the value 0 indicates that it is a land cell, and no fishing can be done there. The objective is to determine the maximum number of fish that a fisher can catch when starting from an optimally chosen water cell. The conditions for fishing are:

  • A fisher can harvest all fish from the water cell he is currently on.
  • The fisher can move from one water cell to any directly adjacent water cell (up, down, left, right), provided it isn't land.
  • The fisher can perform these actions repetitively and in any order.

The desired output is the maximum number of fish that can be caught, with the possibility of a 0 when no water cell (cells with fish) is available.

Intuition

To solve the problem, we need to consider all water regions (areas of connected water cells) and the fish available within them. Since the fisher can only move to adjacent water cells, whenever he moves, he 'engages' a specific water region. It's important to recognize that once a fisher starts fishing in a region, they should catch all the fish in that region before moving to another since returning to a region is not beneficial—fish already caught won't respawn.

We reach an intuitive approach by focusing on the following points:

  • Once the fisher starts at a water cell, they should collect all fish in the connected water region.
  • We should account for all fish present in a standalone water region in one go—there's no coming back for more once they are caught.
  • By iterating over all water cells and simulating this fishing approach, we can find the largest possible catch.

With these points in mind, we turn to Depth-First Search (DFS)—a perfect technique for exploring all cells in a connected region starting from any given water cell. The DFS counts the fish, marks the cells as 0 once visited (to avoid recounting), and moves to adjacent water cells until the entire region is depleted of fish. We keep track of the maximum number of fish caught in any single run of the DFS across the entire grid. By applying this process to each water cell, we can identify the optimal starting cell that yields the most fish.

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

Solution Approach

To achieve the task, we use a recursive Depth-First Search (DFS) algorithm to navigate through the grid. The implementation relies on a helper dfs function that takes the coordinates (i, j) of the current cell and returns the count of fish caught starting from that cell.

Here is the approach broken down:

  1. The dfs function initiates with the grid cell coordinates (i, j) and proceeds to capture all fish at this location. It sets the fish count at this cell to 0 to mark the cell as "fished out" and to prevent revisiting during the same DFS traversal.

  2. We then iterate over the four possible directions (up, down, left, right) to move from the current cell to an adjacent one. This is done efficiently by using a loop and the pairwise utility, iterating over pairs of directional movements encoded as (dx, dy) deltas.

  3. For each potential move to an adjacent cell (x, y), we check if the cell is within bounds of the grid, and if it is a water cell (grid[x][y] > 0). If it fits these criteria, we call the dfs function recursively for that cell.

  4. The counts of fish from the current cell and from recursively applied DFS calls are summed up to get the total count of fish in this connected water region.

  5. The outer loop of the Solution class iterates through all cells (i, j) in the grid. For each water cell identified (grid[i][j] > 0), it invokes the dfs function and captures the return value.

  6. We maintain a variable ans to keep track of the maximum fish count seen so far. Every time we get a count back from a dfs call, we update ans with the maximum of its current value and the newly obtained count.

  7. After the loop completes, we return the value of ans as the result, representing the maximum number of fish that can be caught starting from the best water cell.

The combination of recursive DFS and careful updates ensures that we thoroughly explore each connected water region, never double count, and always remember the "best" starting cell found in terms of fish count.

Mentioned in the Reference Solution Approach, the DFS method inherently works well for this problem because it naturally follows the constraints of the fisher's movement and fishing actions. Furthermore, by traversing and marking cells within the grid, we avoid the need for an auxiliary data structure to keep track of visited cells, thereby utilizing the grid for dual purposes—both as the map of the fishing area and as the record of visited water cells.

Here's the pseudocode that encapsulates this solution:

1function dfs(i, j):
2    cnt = grid[i][j]
3    grid[i][j] = 0  // Mark as visited (fished out)
4    for each direction (up, down, left, right) do:
5        x, y = new coordinates in direction
6        if (x, y) is in bounds and is water cell then:
7            cnt += dfs(x, y)
8    return cnt
9
10for each cell (i, j) in grid do:
11    if grid[i][j] > 0 then:
12        ans = max(ans, dfs(i, j))
13
14return ans

The final external for loop ensures that every water region is considered, while the recursive dfs functions guarantee a thorough exploration of each region.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer technique does Quick Sort use?

Example Walkthrough

Let's take a 3x3 grid to illustrate the solution approach.

1grid = [
2  [2, 3, 1],
3  [0, 0, 4],
4  [7, 6, 0]
5]

In this grid, 0 represents land cells, and non-zero values like 2, 3, 1, etc., represent water cells with the corresponding number of fish in them.

Let's apply the DFS algorithm on the grid.

  1. Starting at the top left corner, (0, 0) has 2 fish. We start here and set grid[0][0] to 0 which now looks like:
1grid = [
2  [0, 3, 1],
3  [0, 0, 4],
4  [7, 6, 0]
5]
  1. From (0, 0), we look at adjacent cells up, down, left and right. Only two cells are adjacent and they are water cells: (0, 1) and (1, 2).

  2. Next, we go to (0, 1), where there are 3 fish. After setting grid[0][1] to 0, the grid is:

1grid = [
2  [0, 0, 1],
3  [0, 0, 4],
4  [7, 6, 0]
5]
  1. From (0, 1), we only have one water cell adjacent which is (0, 2), so we move there and add 1 fish to our count and mark the cell as visited:
1grid = [
2  [0, 0, 0],
3  [0, 0, 4],
4  [7, 6, 0]
5]

This completes the DFS for one water region originating from (0, 0). The total fish caught so far is 2+3+1 = 6 fish.

  1. We then continue the external loop and come across the cell (1, 2) and start a new DFS because grid[1][2] > 0. This cell is isolated and only has 4 fish. After fishing, the grid updates as follows:
1grid = [
2  [0, 0, 0],
3  [0, 0, 0],
4  [7, 6, 0]
5]
  1. Finally, we explore the cell (2, 0), triggering another DFS call. This region includes the cells (2, 0) and (2, 1) with a total of 7 + 6 = 13 fish.
1grid = [
2  [0, 0, 0],
3  [0, 0, 0],
4  [0, 0, 0]
5]

Following these steps, we have the maximum fish counts from each standalone water region:

  • Starting at (0, 0) - we caught 6 fish.
  • Starting at (1, 2) - we caught 4 fish.
  • Starting at (2, 0) - we caught 13 fish.

Our answer ans is the maximum of these, which is 13 fish.

The procedure ensures that we never revisited any water cell and always accounted for the whole region before moving to the next. The final answer is the maximum fish caught across all regions, taking into account that only one region can be fully fished by starting at the optimal water cell.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findMaxFish(self, grid: List[List[int]]) -> int:
5        # Depth-first search function to explore the grid and count fish
6        def dfs(i: int, j: int) -> int:
7            fish_count = grid[i][j]  # Number of fish at the current location
8            grid[i][j] = 0  # Mark the current location as visited by setting it to 0
9            # Explore all four adjacent cells (up, down, left, right)
10            for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
11                x, y = i + dx, j + dy
12                # Check if the new position is within the grid bounds and has fish
13                if 0 <= x < m and 0 <= y < n and grid[x][y]:
14                    fish_count += dfs(x, y)  # Add fish from the neighboring cell
15            return fish_count
16
17        m, n = len(grid), len(grid[0])  # Get the dimensions of the grid
18        max_fish = 0  # Initialize the maximum fish count
19        # Iterate over all cells in the grid
20        for i in range(m):
21            for j in range(n):
22                # If the current cell has fish, perform DFS from here
23                if grid[i][j]:
24                    max_fish = max(max_fish, dfs(i, j))  # Update the maximum fish count
25        return max_fish  # Return the maximum number of fish that can be found in one group
26
27# Example usage:
28# sol = Solution()
29# print(sol.findMaxFish([[2, 1], [1, 1], [0, 1]]))
30
1class Solution {
2  
3    private int[][] grid; // The grid representing the pond.
4    private int rows; // Number of rows in the pond grid.
5    private int cols; // Number of columns in the pond grid.
6
7    // This method calculates the maximum number of fish that can be found in a straight line.
8    public int findMaxFish(int[][] grid) {
9        rows = grid.length; // Assigns the number of rows of the grid.
10        cols = grid[0].length; // Assigns the number of columns of the grid.
11        this.grid = grid; // Stores the grid in the instance variable for easy access.
12        int maxFishCount = 0; // Starts with zero as the maximum number of fish found.
13      
14        // Iterates through each cell in the grid.
15        for (int i = 0; i < rows; ++i) {
16            for (int j = 0; j < cols; ++j) {
17                // If the current cell contains fish, perform a DFS to find all connected fish.
18                if (grid[i][j] > 0) {
19                    maxFishCount = Math.max(maxFishCount, dfs(i, j));
20                }
21            }
22        }
23        // Return the largest group of connected fish found in the pond.
24        return maxFishCount;
25    }
26
27    // This method performs a depth-first search (DFS) to find all connected fish starting from cell (i, j).
28    private int dfs(int i, int j) {
29        int fishCount = grid[i][j]; // Counts the fish at the current cell.
30        grid[i][j] = 0; // Marks the current cell as "visited" by setting its fish count to zero.
31        // Array to calculate adjacent cell coordinates (up, right, down, left).
32        int[] directions = {-1, 0, 1, 0, -1};
33      
34        // Explore all four adjacent cells using the directions array.
35        for (int k = 0; k < 4; ++k) {
36            int x = i + directions[k]; // Row index of the adjacent cell.
37            int y = j + directions[k + 1]; // Column index of the adjacent cell.
38          
39            // Check whether the adjacent cell is within grid bounds and contains fish.
40            if (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] > 0) {
41                fishCount += dfs(x, y); // Accumulate fish count and continue DFS.
42            }
43        }
44        // Return the total count of fish connected to cell (i, j).
45        return fishCount;
46    }
47}
48
1#include <vector>
2#include <algorithm>
3#include <functional>
4
5class Solution {
6public:
7    int findMaxFish(std::vector<std::vector<int>>& grid) {
8        int numRows = grid.size();
9        int numCols = grid[0].size();
10        int maxFishCount = 0;
11
12        // Depth-first search function to search for connected fishes.
13        std::function<int(int, int)> depthFirstSearch = [&](int row, int col) -> int {
14            int fishCount = grid[row][col];
15            grid[row][col] = 0; // Mark as visited by setting to 0.
16
17            // Directions: up, right, down, left
18            int directions[5] = {-1, 0, 1, 0, -1};
19            for (int k = 0; k < 4; ++k) {
20                int newRow = row + directions[k];
21                int newCol = col + directions[k + 1];
22
23                // Check if the new coordinates are valid and not visited.
24                if (newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols && grid[newRow][newCol]) {
25                    fishCount += depthFirstSearch(newRow, newCol); // Recurse.
26                }
27            }
28            return fishCount;
29        };
30
31        // Iterate over each cell in the grid.
32        for (int i = 0; i < numRows; ++i) {
33            for (int j = 0; j < numCols; ++j) {
34                // If cell is not visited and there are fishes, perform DFS.
35                if (grid[i][j]) {
36                    maxFishCount = std::max(maxFishCount, depthFirstSearch(i, j));
37                }
38            }
39        }
40        return maxFishCount; // Return the maximum number of fishes in a connected region.
41    }
42};
43
1function findMaxFish(grid: number[][]): number {
2    const rowCount = grid.length;    // Number of rows in the grid.
3    const colCount = grid[0].length; // Number of columns in the grid.
4
5    // Direction vectors to help navigate through grid neighbors.
6    const directions = [-1, 0, 1, 0, -1]; 
7  
8    // Deep First Search function to count fish in a connected region of the grid.
9    const deepFirstSearch = (row: number, col: number): number => {
10        let count = grid[row][col]; // Start with the initial count of fish in the given cell.
11        grid[row][col] = 0; // Mark the cell as visited by setting it to 0.
12      
13        // Search through all four possible directions: up, right, down, and left.
14        for (let dirIndex = 0; dirIndex < 4; ++dirIndex) {
15            const nextRow = row + directions[dirIndex]; 
16            const nextCol = col + directions[dirIndex + 1];
17          
18            // If the next cell is within the grid bounds and has fish, perform DFS on it.
19            if (nextRow >= 0 && nextRow < rowCount && nextCol >= 0 && nextCol < colCount && grid[nextRow][nextCol] > 0) {
20                count += deepFirstSearch(nextRow, nextCol);
21            }
22        }
23      
24        return count; // Return the total fish count for this region.
25    };
26
27    let maxFish = 0; // Keep track of the maximum fish count found.
28  
29    // Iterate through each cell in the grid.
30    for (let row = 0; row < rowCount; ++row) {
31        for (let col = 0; col < colCount; ++col) {
32            // If the cell is not visited and has fish, use DFS to find total fish count.
33            if (grid[row][col] > 0) {
34                // Update maxFish with the maximum of the current max and newly found count.
35                maxFish = Math.max(maxFish, deepFirstSearch(row, col));
36            }
37        }
38    }
39  
40    return maxFish; // Return the maximum fish count found in any connected region.
41}
42

Time and Space Complexity

Time Complexity

The time complexity of the algorithm is O(m*n) because the dfs function is called for every cell in the grid at most once. Each cell is visited and then it's marked as 0 (zero) to avoid revisiting. Consequently, every cell (where m is the number of rows and n is the number of columns of the grid) is accessed in the worst case.

Space Complexity

The space complexity is O(m*n) in the worst-case scenario, which occurs when the grid is fully filled with non-zero values, leading to the deepest recursion of dfs potentially reaching m*n calls in the call stack before returning.

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


Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄