2658. Maximum Number of Fish in a Grid :- find the maximum fish count

Round 1

Questions:

Question

2658. Maximum Number of Fish in a Grid: Find the maximum fish count.

Step-by-Step Explanation:

1. DFS Helper Function:

   • The function dfs(i, j) explores the grid starting from the cell (i, j).
   • It collects the fish count from the current cell and marks it as visited by setting grid[i][j] = 0.
   • It then recursively explores all four possible directions: up, down, left, and right. If a neighboring cell has fish and is within bounds, it adds the fish count from that region to the total.

2. Iterative Search for Connected Components:

   • The main function iterates through every cell in the grid.
   • If a cell contains fish (grid[i][j] > 0), it triggers the DFS function to calculate the total fish in the connected region starting from that cell.
   • After each DFS call, the maximum fish count is updated using max().

3. Return the Result:

   • The function returns the largest fish count from all connected regions in the grid.

Python Code Implementation:

class Solution(object):
    def findMaxFish(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        def dfs(i, j):
            # Fish count for the current cell
            cnt = grid[i][j]
            # Mark the cell as visited
            grid[i][j] = 0
            # Explore all 4 possible directions: up, down, left, right
            for a, b in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                x, y = i + a, j + b
                # Check if the neighbor is valid and not yet visited
                if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y]:
                    cnt += dfs(x, y)
            return cnt

        # Initialize the dimensions and max fish count
        m, n = len(grid), len(grid[0])
        max_fish = 0
        # Iterate through each cell in the grid
        for i in range(m):
            for j in range(n):
                # If the cell has fish, start a DFS
                if grid[i][j]:
                    max_fish = max(max_fish, dfs(i, j))
        return max_fish

Key Takeaways:

• This problem showcases the use of depth-first search (DFS) to explore connected components in a grid.
• Marking cells as visited during DFS ensures no cell is revisited, preventing infinite loops.
• The approach efficiently handles various edge cases and maintains optimal time complexity.

Complexity Analysis:

1. Time Complexity:

   • Each cell is visited once during the DFS traversal.
   • Overall complexity is O(M * N) where M and N are the dimensions of the grid.

2. Space Complexity:

   • The recursive DFS function uses stack space proportional to the size of the grid in the worst case.
   • Space complexity is O(M * N).