Maximum Number Of Fish In the grid - Easy Solution - Nice Explanation ‼️💯
Intuition

We can use bfs to keep track of the adjacent cells and once the cell is visited,it's marked as 0 in-place.


At each bfs,we'll obtain max number of f
# Intuition
1. We can use bfs to keep track of the adjacent cells and once the cell is visited,it's marked as 0 in-place.

1. At each bfs,we'll obtain max number of fishes, so that we'll get the maximum of the fishes that can be obtained in the grid.
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach

**findMaxFish**: 

**parameter**: grid (2-D integer array).
**return value**: int

**Initialization**:

Initialize row to be the length of the grid ,col to be the length of each row and maxFish is set to 0 initially.

    int row=grid.length;
    int col=grid[0].length;
    int maxFish=0;

**Perform bfs**:

Iterate through all the cells in the grid 2-D array.

    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){

Perform bfs on the grid 2-D array if it is not the land cell and obtain the maximum number of fishes possible.

    if(grid[i][j]>0){
        int fishReg=bfs(grid,row,col,i,j);

Each bfs will return the fish in that region, compare that at each iteration and return the maximum number of fishes.
 
    maxFish=Math.max(maxFish,fishReg);

**Returning the result**:

Return maxFish which contains maximum number of fishes that can be obtained from the given grid.

    return maxFish;

**bfs**:

**parameter**: grid (2-D integer array), row, col, i and j of integer.
**return value**: int.

**Base Condition**:

If i is not within the range of 0 to row or j is not within the range of 0 to col or the cell is the land,then stop recursion and return 0.

    if(i<0 || i>=row || j<0 || j>=col  || grid[i][j]==0)
    {
        return 0;
    }

**Perform bfs for fish count**:

Initialize fish to be the fishes in the particular cell of grid at index i and j.

    int fish=grid[i][j];

If used, mark the cell as 0.

    grid[i][j]=0;

Visit the adjacent cells of the grid by bfs and increment the fish count.

    fish+=bfs(grid,row,col,i+1,j);
    fish+=bfs(grid,row,col,i-1,j);

    fish+=bfs(grid,row,col,i,j+1);
    fish+=bfs(grid,row,col,i,j-1);

**Returning the result**:

Return fish which contains the fish at the region of the grid at index i and j.

    return fish;
<!-- Describe your approach to solving the problem. -->

# Complexity
- ***Time complexity***: **O(mxn)**.
  
   m -> number of rows in the grid.
   n -> number of columns in the grid.

**Outer Loops**: **O(mxn)**.

The two nested for loops in the findMaxFish function iterate over all cells of the grid.

For grid size mxn, the total time complexity of these loops are **O(mxn)**.

**bfs function**: **O(mxn)**.

Each cell is visited once during the DFS traversal. When a cell is visited, it is marked as 0 (visited), so it is not revisited.

In the worst case, all cells are part of one large connected component. Here, the DFS would visit every cell in the grid.Hence it takes **O(mxn) time**.

**Total Time Complexity**: **O(mxn)**.

The bfs function is called for every unvisited cell that has a positive value. Since each cell is visited exactly once, the total work done is proportional to the number of cells in the grid.

Thus the total time complexity is **O(mxn)**.

<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- ***Space complexity***: **O(mxn)**.

   m -> number of rows in the grid.
   n -> number of columns in the grid.

**Recursive Depth**: **O(mxn)**.

The bfs function uses recursion to perform DFS. The recursion depth corresponds to the **size of the largest connected component** of non-zero cells.

In the worst case, all cells are part of one large connected component, resulting in a recursion depth of O(mxn).Hence it consumes **O(mxn) space**.

**Auxillary Space**: **O(1)**.

No additional data structures are used, and the grid itself is modified in-place to mark visited cells.

Hence, the **auxiliary space is negligible** (O(1)).

**Total Space Complexity**: **O(mxn)**.

Total Space Complexity is **dominated by the recursive depth**.Hence the total Space Complexity is **O(mxn)**.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    int max;
    private int bfs(int[][] grid,int row,int col,int i,int j)
    {
        if(i<0 || i>=row || j<0 || j>=col  || grid[i][j]==0)
        {
            return 0;
        }
        
        int fish=grid[i][j];

        grid[i][j]=0;

        fish+=bfs(grid,row,col,i+1,j);
        fish+=bfs(grid,row,col,i-1,j);

        fish+=bfs(grid,row,col,i,j+1);
        fish+=bfs(grid,row,col,i,j-1);

        return fish;
    }
    public int findMaxFish(int[][] grid) {
        int row=grid.length;
        int col=grid[0].length;
        int maxFish=0;

        for(int i=0;i<row;i++)
        {
            for(int j=0;j<col;j++)
            {
                if(grid[i][j]>0)
                {
                    int fishReg=bfs(grid,row,col,i,j);
                    maxFish=Math.max(maxFish,fishReg);
                }
            }
        }

        return maxFish;
    }
}
```
['Array', 'Breadth-First Search', 'Matrix', 'Java']