We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Fish in a Grid

Number: 2764

Difficulty: Medium

Paid? No

Companies: Microsoft, Meta, Amazon, Google, Adobe

Problem Description

Given a grid representing water cells (with a positive number indicating the number of fish) and land cells (zero), determine the maximum number of fish a fisher can catch by starting at some water cell and moving to adjacent water cells (up, down, left, right). The goal is to compute the sum of fish over a connected component of water cells, and the fisher collects all fish in that component by visiting each cell once. Return 0 if no water cell exists.

Key Insights

  • The problem is about finding the maximum sum over all connected components in the matrix.
  • Each water cell (grid value > 0) can be visited, and adjacent cells (up, down, left, right) are only accessible if they are also water cells.
  • Flood fill using Depth-First Search (DFS) or Breadth-First Search (BFS) can be employed to traverse each connected component.
  • Mark visited cells to avoid double counting.
  • Since grid dimensions are small (m, n <= 10), either DFS or BFS is efficient.

Space and Time Complexity

Time Complexity: O(m * n) — Each cell is visited once. Space Complexity: O(m * n) — In the worst case, the recursion stack (for DFS) or queue (for BFS) holds all cells.

Solution

We iterate through each cell in the grid. For every unvisited water cell, we start a DFS (or BFS) that sums all the fish in the connected component. We mark each visited cell to ensure it's not processed again. Finally, the answer is the maximum total fish collected from any connected component. We use a grid traversal, simple recursion (for DFS), and a visited marker (either an auxiliary matrix or in-place modification if allowed).

Code Solutions

# Python solution using DFS with detailed comments
def findMaxFish(grid):
    # Dimensions of grid
    m, n = len(grid), len(grid[0])
    
    # Function to perform DFS from cell (r, c)
    def dfs(r, c):
        # Check for out-of-bound indices or if the cell is not water (0) 
        # In this context, 0 means land or already visited water cell.
        if r < 0 or c < 0 or r >= m or c >= n or grid[r][c] == 0:
            return 0
        # Sum fish in current cell
        fish_count = grid[r][c]
        # Mark this cell as visited by setting it to 0 (or another marker)
        grid[r][c] = 0
        # Explore adjacent cells (up, down, left, right)
        fish_count += dfs(r - 1, c)
        fish_count += dfs(r + 1, c)
        fish_count += dfs(r, c - 1)
        fish_count += dfs(r, c + 1)
        return fish_count

    max_fish = 0
    # Iterate over each cell in the grid
    for i in range(m):
        for j in range(n):
            # Only start DFS for water cells (grid[i][j] > 0)
            if grid[i][j] > 0:
                max_fish = max(max_fish, dfs(i, j))
    return max_fish

# Example usage:
# grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
# print(findMaxFish(grid))  # Expected output: 7
← Back to All Questions