LeetCode 2658: Maximum Number of Fish in a Grid Solution

Master LeetCode problem 2658 (Maximum Number of Fish in a Grid), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2658. Maximum Number of Fish in a Grid

Medium

Array Depth-First Search Breadth-First Search Union Find Matrix

Problem Explanation

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.

Solution Code

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));
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2658 (Maximum Number of Fish in a Grid)?

This page provides optimized solutions for LeetCode problem 2658 (Maximum Number of Fish in a Grid) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2658 (Maximum Number of Fish in a Grid)?

The time complexity for LeetCode 2658 (Maximum Number of Fish in a Grid) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2658 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2658 in Java, C++, or Python.

Back to LeetCode Solutions