Problem of The Day: Maximum Number of Fish in a Grid

Problem Statement

Intuition

The problem requires finding the maximum sum of fish in any connected water region. The idea is to check each cell and, if it contains fish, explore all connected cells to calculate the total fish in that region. The maximum sum across all regions is the answer.

Approach

The approach iterates over each cell in the grid. For cells with fish, a depth-first search (DFS) is performed to mark all reachable cells (connected via adjacent cells with fish). After the DFS, the sum of fish in all visited cells is calculated, and the maximum sum is updated. Note that this approach may revisit the same region multiple times, as each cell in a region triggers a separate DFS. However, this ensures that all possible regions are considered, even if overlapping.

Complexity

• Time complexity: O((R * C)^2)

In the worst case, for each cell (RC cells), a DFS (O(RC)) and a sum calculation (O(RC)) are performed, leading to O((RC)^2) time.

• Space complexity: O(R * C)

The space is used for the visited matrix during each DFS, which requires O(R*C) space.

Code

class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        directions = [(0,1),(1,0),(0,-1),(-1,0)]
        ROWS = len(grid)
        COLS = len(grid[0])
        res = 0

        def dfs(row, col, visited):
            visited[row][col] = True
            for x, y in directions:
                r, c = row + x, col + y
                if 0 <= r < ROWS and 0 <= c < COLS and not visited[r][c] and grid[r][c] > 0:
                    dfs(r, c, visited)

        for row in range(ROWS):
            for col in range(COLS):
                if grid[row][col] > 0:
                    visited = [[False for _ in range(COLS)] for _ in range(ROWS)]
                    dfs(row, col, visited)
                    curr = 0
                    for r in range(ROWS):
                        for c in range(COLS):
                            if visited[r][c]:
                                curr += grid[r][c]
                    res = max(res, curr)

        return res