2658. Maximum Number of Fish in a Grid

Explanation

To solve this problem, we can use a Depth-First Search (DFS) approach to explore all possible paths starting from each water cell. At each step of the DFS traversal, we can either catch the fish at the current cell and continue exploring or move to one of the adjacent water cells. We need to keep track of the maximum number of fish caught so far during the traversal.

Algorithm:

Iterate through all cells in the grid.
For each water cell encountered, start a DFS traversal from that cell to explore all possible paths.
During the DFS traversal, track the total number of fish caught.
Return the maximum number of fish caught across all starting water cells.

Time Complexity: The time complexity of the DFS traversal is O(m * n) where m is the number of rows and n is the number of columns in the grid.

Space Complexity: The space complexity is O(m * n) due to the recursive stack space used in the DFS traversal.

View Leetcode Problem

class Solution {
    public int getMaximumFish(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) {
                    maxFish = Math.max(maxFish, dfs(grid, i, j));
                }
            }
        }

        return maxFish;
    }

    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return 0;
        }

        int fish = grid[i][j];
        grid[i][j] = 0;

        int up = dfs(grid, i - 1, j);
        int down = dfs(grid, i + 1, j);
        int left = dfs(grid, i, j - 1);
        int right = dfs(grid, i, j + 1);

        grid[i][j] = fish;

        return fish + Math.max(Math.max(up, down), Math.max(left, right));
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.