LeetCode, 𝐃𝐚𝐲-28/365-DSA-Coding 𝐉𝐨𝐮𝐫𝐧𝐞𝐲…Google Prep…

Today I Learned This Problem: 2658. Maximum Number of Fish in a Grid

Problem Overview

The problem involves finding the maximum number of fish you can collect in a grid. Given:

• A 2D grid of integers, where each cell contains either a non-negative integer (indicating the number of fish) or 0 (indicating no fish).
• Starting from any non-zero cell, you can move up, down, left, or right, collecting all the fish from connected non-zero cells.

The goal is to determine the maximum number of fish that can be collected in one connected component of the grid.

Challenges Involved

1. Connected Components: Identifying connected groups of non-zero cells in the grid.
2. Depth-First Search (DFS): Using recursion to explore all adjacent cells in a connected component.
3. State Modification: Marking cells as visited to prevent revisiting them.
4. Optimization: Ensuring the DFS is efficient for larger grids.

Explanation

This problem can be solved using Depth-First Search (DFS) to traverse connected components in the grid. The key steps include:

1. Traverse the Grid: Loop through all cells in the grid. When a non-zero cell is found, initiate a DFS to explore and collect fish from all reachable cells in the connected component.
2. DFS Implementation:

• For each cell (i, j), add the fish count to the total.
• Mark the cell as visited by setting it to 0.
• Recursively move to adjacent cells (up, down, left, right) if they contain fish.

1. Track Maximum Fish: Maintain a variable to store the maximum fish collected from any single connected component.

My Solution Approach

1. Grid Dimensions and Directions:

• Determine grid size (m, n) and define movement directions ([-1, 0, 1, 0, -1] for up, down, left, right).

1. Depth-First Search Function:

• Base Case: Stop recursion if the cell is out of bounds or has no fish.
• Recursive Case: Collect fish, mark the cell as visited, and recursively explore neighboring cells.

1. Iterate Through the Grid:

• For each cell in the grid, if it contains fish, perform a DFS and update the maximum fish count.

Python Code

class Solution:
    def findMaxFish(self, grid):
        m, n = len(grid), len(grid[0])  # Grid dimensions
        directions = [-1, 0, 1, 0, -1]  # Movement directions (up, right, down, left)
        
        # Depth-First Search to calculate fish in a connected component
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 0:
                return 0
            fish = grid[i][j]
            grid[i][j] = 0  # Mark cell as visited
            for k in range(4):  # Explore all 4 directions
                fish += dfs(i + directions[k], j + directions[k + 1])
            return fish
        
        max_fish = 0
        # Iterate over the grid
        for i in range(m):
            for j in range(n):
                if grid[i][j] > 0:  # Start DFS if cell contains fish
                    max_fish = max(max_fish, dfs(i, j))
        return max_fish

Other Possible Solutions

1. Breadth-First Search (BFS):

• Use a queue to explore connected components level by level.
• BFS can be used instead of DFS to achieve the same result but may involve more overhead for maintaining the queue.

1. Union-Find (Disjoint Set Union):

• Preprocess the grid to group connected cells into disjoint sets.
• Calculate the total fish in each set and find the maximum.
• This approach can be efficient but requires additional space and preprocessing logic.

Learnings

• DFS Techniques: Enhanced understanding of recursive traversal and grid-based problem-solving.
• Connected Component Analysis: Identifying and analyzing groups of related cells in a matrix.
• Optimization: Learned how to modify state in-place to improve space efficiency.

Real-Life Usage

1. Flood Fill Algorithms: Used in image editing and gaming (e.g., detecting regions of a map).
2. Ecosystem Simulation: Modeling and analyzing animal movements in habitats.
3. Data Clustering: Grouping connected data points in large datasets.

To Sum Up…

This problem was a fun exercise in DFS and grid traversal. It improved my problem-solving skills in recursive algorithms and optimization. If you have alternative approaches or feedback, feel free to share!