✅ Easy to Understand | Graph Theory | DFS | Connected Components | Detailed Video Explanation 🔥
IntuitionThe problem can be visualized as finding the maximum sum of fish in connected regions of a grid, where each region is defined by non-zero cells that ar
# Intuition
The problem can be visualized as finding the maximum sum of fish in connected regions of a grid, where each region is defined by non-zero cells that are adjacent (either vertically or horizontally). A depth-first search (DFS) is well-suited for exploring such connected regions, as it allows us to traverse all reachable cells in a region systematically while marking them as visited.

# Approach
1. **Grid Traversal**: Iterate through each cell in the grid.
2. **DFS for Connected Regions**: For each cell with a non-zero value, initiate a DFS to calculate the total fish in the connected region. 
   - During the DFS, add the value of the current cell to a temporary variable (`temp`) and mark the cell as visited by setting its value to `0`.
   - Recursively explore all adjacent cells (up, down, left, right) that are within bounds and not yet visited.
3. **Track Maximum Fish**: After completing the DFS for a region, compare the collected fish (`temp`) with the current maximum (`max`) and update `max` if necessary.
4. **Return Result**: After processing all cells, return the maximum fish collected (`max`).

# Complexity
- **Time complexity**:  
  $$O(m \times n)$$  
  - Each cell in the grid is visited exactly once during the traversal and DFS. Thus, the total time complexity is proportional to the number of cells in the grid.

- **Space complexity**:  
  $$O(m \times n)$$ (in the worst case, for the recursion stack)  
  - In the worst-case scenario, where the grid forms a single large connected region, the recursion stack may grow to contain all cells in the grid.


# Code
```java []
class Solution {
    // Variables to store the maximum number of fish collected and temporary fish count for a region
    int max;
    int temp;
    
    // Dimensions of the grid
    int m, n;
    
    // Directions for moving up, down, left, and right
    int[][] dir = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    
    // Grid to represent the fishing area
    int[][] grid;

    // Method to find the maximum fish that can be collected
    public int findMaxFish(int[][] grid) {
        this.grid = grid; // Initialize the grid
        max = 0; // Initialize the maximum fish count to 0

        m = grid.length; // Number of rows
        n = grid[0].length; // Number of columns

        // Iterate through each cell in the grid
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // If the cell has fish, start a DFS from there
                if (grid[i][j] != 0) {
                    temp = 0; // Reset the temporary fish count for the current region
                    dfs(i, j); // Perform a DFS to collect all fish in the connected region
                    
                    // Update the maximum fish count if the current region has more fish
                    if (temp > max)
                        max = temp;
                }
            }
        }
        return max; // Return the maximum fish count
    }

    // Depth-First Search (DFS) to collect fish in a connected region
    private void dfs(int i, int j) {
        // Base case: If out of bounds or the cell is empty, return
        if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0)   
            return;

        temp += grid[i][j]; // Add the fish in the current cell to the temporary count
        grid[i][j] = 0; // Mark the cell as visited by setting it to 0

        // Explore all 4 possible directions
        for (int[] d : dir) {
            int ii = i + d[0]; // Calculate the new row index
            int jj = j + d[1]; // Calculate the new column index
            dfs(ii, jj); // Recursively perform DFS in the new direction
        }
    }
}

```

LeetCode 2658 Maximum Number of Fish in a Grid | Graph Theory | Easy | DFS | Asked in Adobe
https://youtu.be/NK71iQVoPO4


['Array', 'Depth-First Search', 'Breadth-First Search', 'Matrix', 'Java']