Maximum Number of Fish in a Grid

Medium

Asked by:

21 views

Topics:

Graphs

You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:

A land cell if grid[r][c] = 0, or
A water cell containing grid[r][c] fish, if grid[r][c] > 0.

A fisher can start at any water cell (r, c) and can do the following operations any number of times:

Catch all the fish at cell (r, c), or
Move to any adjacent water cell.

Return the maximum number of fish the fisher can catch if he chooses his starting cell optimally, or 0 if no water cell exists.

An adjacent cell of the cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) or (r - 1, c) if it exists.

Example 1:

Input: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
Output: 7
Explanation: The fisher can start at cell (1,3) and collect 3 fish, then move to cell (2,3) and collect 4 fish.

Example 2:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
Output: 1
Explanation: The fisher can start at cells (0,0) or (3,3) and collect a single fish.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10
0 <= grid[i][j] <= 10

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the grid (number of rows and columns)?
Can the fish counts in the grid cells be zero or negative?
If there are multiple disconnected groups of fish, do I need to return the maximum number of fish from any one group, or something else?
What should I return if the grid is empty (0x0) or null?
Is it guaranteed that all fish counts are integers, or could they be floating-point numbers?

Brute Force Solution

Approach

We want to find the maximum number of fish we can catch by visiting connected squares on a grid. The brute force method involves exploring every single possible path of connected squares and calculating the total fish we'd catch on that path.

Here's how the algorithm would work step-by-step:

Start at one square on the grid.
Check all its neighboring squares (up, down, left, and right).
For each neighbor, consider it as the next square in our path and add the fish from that square to our total.
From that neighbor, again check all its unvisited neighbors and repeat the process of adding fish.
Continue this process, exploring every possible path until we can't go any further (either we hit the edge of the grid or all neighbors have already been visited).
Once a path is complete, remember the total number of fish caught along that path.
Repeat this entire process starting from every single square on the grid to ensure we've considered all possibilities.
After exploring all possible paths from all starting squares, compare all the totals we recorded.
The highest total represents the maximum number of fish we can catch by visiting connected squares.

Code Implementation

def max_fish_brute_force(grid):
    rows = len(grid)
    cols = len(grid[0])
    maximum_fish = 0

    def explore_path(row, col, current_fish, visited):
        nonlocal maximum_fish

        #Add the fish at current location to the current path
        current_fish += grid[row][col]
        maximum_fish = max(maximum_fish, current_fish)

        #Define possible directions to explore
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        for delta_row, delta_col in directions:
            new_row = row + delta_row
            new_col = col + delta_col

            #Check that the new location is valid before proceeding
            if 0 <= new_row < rows and 0 <= new_col < cols and (new_row, new_col) not in visited:
                explore_path(new_row, new_col, current_fish, visited | {(new_row, new_col)})

    for start_row in range(rows):
        for start_col in range(cols):
            # Start exploring from every cell in the grid.
            explore_path(start_row, start_col, 0, {(start_row, start_col)})

    return maximum_fish

Big(O) Analysis

Time Complexity

O(4^(n*m)) – The algorithm explores all possible paths in the grid using a recursive approach. In the worst-case scenario, from each cell, we might have up to four possible directions to move (up, down, left, right). The grid size is n rows by m columns, so there are n*m cells. Since each cell can potentially have 4 choices and we could potentially visit each cell in the grid, the time complexity grows exponentially with the size of the grid. Therefore, in the worst case, the time complexity approaches O(4^(n*m)). This is because at each cell, we could potentially explore all possible combinations of paths of length up to n*m.

Space Complexity

O(N) – The described brute force algorithm uses recursion to explore all possible paths. In the worst-case scenario, the algorithm might explore a path that visits almost every square in the grid before backtracking, leading to a maximum recursion depth proportional to the number of squares, N, where N is the total number of cells in the grid. Each recursive call adds a new frame to the call stack. Additionally, to avoid revisiting cells in a path, the algorithm implicitly needs to 'keep track of visited locations,' which can be implemented using a boolean array of size N to mark visited cells. Thus, the space complexity is dominated by the recursion depth and the visited array, both contributing O(N) space. Therefore, the overall space complexity is O(N).

Optimal Solution

Approach

The best way to find the most fish is to think of the grid as separate ponds and then add up the fish in the biggest ponds. We want to explore connected areas of fish efficiently and avoid counting the same area twice. This is achieved using a technique that explores adjacent areas of fish and marks them as visited.

Here's how the algorithm would work step-by-step:

Go through each square of the grid one by one.
If a square has fish and we haven't visited it before, consider it the start of a new pond.
Explore all the squares that are connected to this square (horizontally or vertically) and also have fish. This is like finding all the fish in the same pond.
As you explore, keep a running total of the number of fish in this pond.
Mark each square you visit as 'visited' so you don't count it again when you are checking other squares later.
Once you've explored the entire pond, remember the total number of fish you found in it.
Repeat this process for every unvisited square with fish.
Finally, find the largest number of fish among all the ponds you discovered. That's the maximum number of fish you can get from one pond.

Code Implementation

def maximum_number_of_fish_in_grid(grid):
    rows = len(grid)
    cols = len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    max_fish = 0

    def depth_first_search(row, col):
        if row < 0 or row >= rows or col < 0 or col >= cols or\
           visited[row][col] or grid[row][col] == 0:
            return 0

        visited[row][col] = True
        fish_count = grid[row][col]

        # Explore adjacent cells to find connected fish.
        fish_count += depth_first_search(row + 1, col)

        fish_count += depth_first_search(row - 1, col)

        fish_count += depth_first_search(row, col + 1)

        fish_count += depth_first_search(row, col - 1)
        return fish_count

    for row_index in range(rows):
        for col_index in range(cols):
            # Only explore unvisited cells with fish.
            if grid[row_index][col_index] != 0 and not visited[row_index][col_index]:

                current_fish_count = depth_first_search(row_index, col_index)

                # Update max_fish if the current pond has more fish.
                max_fish = max(max_fish, current_fish_count)

    return max_fish

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each cell of the grid once, where n is the number of rows and m is the number of columns. For each cell, in the worst case, the depth-first search (DFS) might explore all adjacent cells that contain fish. However, each cell is visited at most once because it's marked as visited, preventing revisits. Therefore, the time complexity is bounded by the number of cells in the grid, which is n * m, resulting in O(n*m). If n and m are equal, we often say O(n^2).

Space Complexity

O(N) – The primary auxiliary space is used by the 'visited' marking. In the worst-case scenario, where the entire grid is filled with fish, we need to mark every square as visited. If N represents the total number of squares in the grid (rows * columns), then the visited marking (which could be a boolean matrix or a set of coordinates) will require space proportional to N. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 immediately as there are no fish to collect.
Grid with only one cell	Return the value of that single cell, as it's the maximum possible fish.
Grid with all zero values	Return 0, as no fish can be collected from any cell.
Grid with all identical non-zero values	Start from any cell and the entire grid's sum will be the result if cells are connected.
Grid with large dimensions (scalability)	DFS/BFS should be implemented iteratively to avoid stack overflow issues and optimize for space complexity.
Grid with disconnected regions of fish	The algorithm needs to explore each unvisited cell to find the maximum fish count among all disconnected components.
Integer overflow when summing fish in large connected regions	Use a 64-bit integer type to store the sum of fish to prevent overflow during DFS/BFS.
Negative fish values in the grid (invalid input)	Handle gracefully: either treat negative values as 0 or throw an exception, depending on the requirements.

Null or empty grid

How to Handle:

Return 0 immediately as there are no fish to collect.

Grid with only one cell

How to Handle:

Return the value of that single cell, as it's the maximum possible fish.

Grid with all zero values

How to Handle:

Return 0, as no fish can be collected from any cell.

Grid with all identical non-zero values

How to Handle:

Start from any cell and the entire grid's sum will be the result if cells are connected.

Grid with large dimensions (scalability)

How to Handle:

DFS/BFS should be implemented iteratively to avoid stack overflow issues and optimize for space complexity.

Grid with disconnected regions of fish

How to Handle:

The algorithm needs to explore each unvisited cell to find the maximum fish count among all disconnected components.

Integer overflow when summing fish in large connected regions

How to Handle:

Use a 64-bit integer type to store the sum of fish to prevent overflow during DFS/BFS.

Negative fish values in the grid (invalid input)

How to Handle:

Handle gracefully: either treat negative values as 0 or throw an exception, depending on the requirements.