Scale Engineer

Maximum Number of Fish in a Grid

Med
#2415Time: O(m^2 * n^2), where `m` is the number of rows and `n` is the number of columns. The outer loops iterate through all `m * n` cells. For each water cell, we initiate a DFS traversal. In the worst case (a grid full of water), the DFS traversal visits `m * n` cells. This results in a total complexity of `O((m * n) * (m * n))`.Space: O(m * n). For each traversal started from the main loop, a new `visited` array of size `m x n` is created. Additionally, the recursion stack for DFS can go up to `m * n` deep in the worst case (a snake-like path through the grid).
Algorithms
Depth-First SearchBreadth-First SearchUnion Find
Data structures
ArrayMatrix

Prompt

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:

(1,3)

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every cell in the grid. If a cell contains water (i.e., has fish), it is considered a potential starting point. For each such potential starting point, a new traversal (like Depth-First Search or DFS) is initiated to find all reachable water cells and sum up the fish. This process is repeated for every water cell, and the maximum sum found across all starting points is returned.

Algorithm

  • Initialize maxFish = 0.
  • Iterate through each cell (r, c) from (0, 0) to (m-1, n-1).
  • If grid[r][c] > 0:
    • Create a new boolean[][] visited array of size m x n and initialize all its values to false.
    • Call a traversal function (e.g., DFS) starting from (r, c) to calculate the total fish in the connected component. Let this be currentFish.
    • The DFS function works as follows:
      • Base case: If the cell is out of bounds, is land, or has been visited, return 0.
      • Mark the current cell as visited.
      • Initialize a local sum with the fish in the current cell.
      • Recursively call DFS for all four adjacent cells (up, down, left, right) and add the results to the local sum.
      • Return the local sum.
    • Update maxFish = max(maxFish, currentFish).
  • After the loops complete, return maxFish.

Walkthrough

The main idea is to test every possible starting water cell and calculate the total fish that can be caught from that start.

We initialize a variable maxFish to 0. We then loop through each cell (r, c) of the m x n grid. If grid[r][c] > 0, it's a water cell and a valid starting point. From this cell (r, c), we start a traversal to find the total fish in its connected component. To do this, we must keep track of visited cells for this specific traversal to avoid infinite loops and recounting fish. So, we create a new boolean[][] visited array for each call from the main loop.

A recursive DFS function is a good fit here. The DFS function would take the current cell's coordinates, the grid, and the visited array. It would add the fish from the current cell, mark it as visited, and then recursively call itself for all adjacent, unvisited water cells. The sum returned by the traversal from (r, c) is compared with maxFish, and maxFish is updated if the new sum is larger. After checking all cells in the grid, maxFish will hold the maximum possible catch.

class Solution {    public int findMaxFish(int[][] grid) {        int maxFish = 0;        int m = grid.length;        int n = grid[0].length;         for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] > 0) {                    // For each water cell, start a new traversal                    boolean[][] visited = new boolean[m][n];                    int currentFish = dfs(i, j, grid, visited);                    maxFish = Math.max(maxFish, currentFish);                }            }        }        return maxFish;    }     private int dfs(int r, int c, int[][] grid, boolean[][] visited) {        int m = grid.length;        int n = grid[0].length;         // Check bounds and if the cell is valid (water and not visited)        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {            return 0;        }         // Mark as visited for this traversal        visited[r][c] = true;        int fishCount = grid[r][c];         // Explore neighbors        fishCount += dfs(r + 1, c, grid, visited);        fishCount += dfs(r - 1, c, grid, visited);        fishCount += dfs(r, c + 1, grid, visited);        fishCount += dfs(r, c - 1, grid, visited);         return fishCount;    }}

Complexity

Time

O(m^2 * n^2), where `m` is the number of rows and `n` is the number of columns. The outer loops iterate through all `m * n` cells. For each water cell, we initiate a DFS traversal. In the worst case (a grid full of water), the DFS traversal visits `m * n` cells. This results in a total complexity of `O((m * n) * (m * n))`.

Space

O(m * n). For each traversal started from the main loop, a new `visited` array of size `m x n` is created. Additionally, the recursion stack for DFS can go up to `m * n` deep in the worst case (a snake-like path through the grid).

Trade-offs

Pros

  • Simple to conceptualize: for every possible start, find the total catch.

  • Correctly solves the problem.

Cons

  • Highly inefficient due to redundant computations. The same connected component of water is traversed and its fish summed up multiple times, once for each cell within that component.

Solutions

class Solution {private  int[][] grid;private  int m;private  int n;public  int findMaxFish(int[][] grid) {    m = grid.length;    n = grid[0].length;    this.grid = grid;    int ans = 0;    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        if (grid[i][j] > 0) {          ans = Math.max(ans, dfs(i, j));        }      }    }    return ans;  }private  int dfs(int i, int j) {    int cnt = grid[i][j];    grid[i][j] = 0;    int[] dirs = {-1, 0, 1, 0, -1};    for (int k = 0; k < 4; ++k) {      int x = i + dirs[k], y = j + dirs[k + 1];      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {        cnt += dfs(x, y);      }    }    return cnt;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem