Maximum Number of Fish in a Grid - Solution Explanation and Code (Video Solution Available)
Video SolutionIntuitionThe problem involves finding the maximum number of fishes that can be collected from connected cells in a grid. My initial thought was to
# Video Solution
[https://youtu.be/yOZ5-C8XFm4?si=hBbCvNYVg-WNPCY-]()
# Intuition
The problem involves finding the maximum number of fishes that can be collected from connected cells in a grid. My initial thought was to treat this as a graph traversal problem, where each cell in the grid represents a node, and edges connect adjacent non-zero cells. This led to using a Breadth-First Search (BFS) approach to explore connected regions.

# Approach
1. Iterate through all cells in the grid.
2. If a cell contains fish (`grid[i][j] != 0`) and has not been visited, perform a BFS to explore the entire connected region starting from that cell.
3. During BFS, maintain a count of the total number of fishes in the connected region.
4. Keep track of the maximum fish count encountered during the traversal.
5. Return the maximum fish count.

# Complexity
- **Time complexity**:  
  $$O(m \times n)$$, where $$m$$ is the number of rows and $$n$$ is the number of columns. Each cell is visited once during the traversal.
  
- **Space complexity**:  
  $$O(m \times n)$$, due to the `visited` array and the queue used in BFS.

# Code
```java
class Solution {
    public int findMaxFish(int[][] grid) {
        int numRows = grid.length, numCols = grid[0].length, result = 0;
        boolean[][] visited = new boolean[numRows][numCols];

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                if (grid[i][j] != 0 && !visited[i][j]) {
                    result = Math.max(result, countFishes(grid, visited, i, j));
                }
            }
        }
        return result;
    }

    private int countFishes(int[][] grid, boolean[][] visited, int row, int col) {
        int numRows = grid.length, numCols = grid[0].length, fishCount = 0;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { row, col });
        visited[row][col] = true;

        int[] rowDirections = { 0, 0, 1, -1 };
        int[] colDirections = { 1, -1, 0, 0 };

        while (!q.isEmpty()) {
            int[] cell = q.poll();
            row = cell[0];
            col = cell[1];
            fishCount += grid[row][col];

            for (int i = 0; i < 4; i++) {
                int newRow = row + rowDirections[i];
                int newCol = col + colDirections[i];
                if (
                    0 <= newRow &&
                    newRow < numRows &&
                    0 <= newCol &&
                    newCol < numCols &&
                    grid[newRow][newCol] != 0 &&
                    !visited[newRow][newCol]
                ) {
                    q.add(new int[] { newRow, newCol });
                    visited[newRow][newCol] = true;
                }
            }
        }
        return fishCount;
    }
}
['Java']