Daily Leetcode – 2658

Probem Description

You are given a 0-indexed 2D matrix grid of size m x n, where each cell (r, c) can represent:

• Land cell: grid[r][c] = 0
• Water cell: grid[r][c] > 0, containing fish.

A fisher can start at any water cell (r, c) and perform the following operations any number of times:

• Catch all the fish at cell (r, c).
• Move to any adjacent water cell.

The task is to determine the maximum number of fish the fisher can catch if they start optimally, or 0 if no water cells exist.

My Solution

This problem can be solved using Depth-First Search (DFS). We iterate through every cell of the grid, and if the cell contains fish (grid[r][c] > 0), we perform DFS to explore the connected region of water cells. During this process, we:

1. Accumulate the number of fish in the connected water cells.
2. Mark visited cells by setting their value to 0 (convert them to land) to avoid double counting.
3. Track the maximum number of fish collected across all possible starting cells.

Here's an implementation in C++

class Solution {
public:
    int findMaxFish(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        int maxFish = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] > 0) {
                    maxFish = max(maxFish, dfs(i,j,grid));
                }
            }
        }

        return maxFish;
    }

    int dfs(int i, int j, vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        stack<pair<int,int>> st;
        st.push({i,j});

        int totalFish = 0;
        while(!st.empty()) {
            auto [i, j] = st.top(); st.pop();

            totalFish += grid[i][j];
            grid[i][j] = 0;

            if(i+1 < m && grid[i+1][j] > 0) st.push({i+1,j});
            if(i-1 >= 0 && grid[i-1][j] > 0) st.push({i-1,j});
            if(j+1 < n && grid[i][j+1] > 0) st.push({i,j+1});
            if(j-1 >= 0 && grid[i][j-1] > 0) st.push({i,j-1});
        }

        return totalFish;
    }
};

Algorithm Analysis

Time Complexity:

The algorithm visits each cell once, so the time complexity is O(n * m) where n is the number of rows and m is the number of columns. DFS traverses connected components of water cells, but since every cell is visited once, the overall complexity remains linear in the size of the grid.

Space Complexity:

The space complexity is determined by the DFS stack, which could be O(n * m) in the worst case (all water cells are connected).

Results

The initial implementation produced the following results:

• Runtime: 19 ms, beating 31.87% of submissions.
• Memory Usage: 107.88 MB, beating 24.87% of submissions.

Optimization

After analyzing other solutions, I found a more efficient DFS approach:

int dfs(int i, int j, vector<vector<int>>& grid, int n, int m) {
    int fish = grid[i][j];
    grid[i][j] = 0;

    int dr[] = {0, 1, 0, -1, 0};  // Combines row and column directions.
    for (int k = 0; k < 4; k++) {
        int nr = i + dr[k];
        int nc = j + dr[k + 1];
        if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] > 0) {
            fish += dfs(nr, nc, grid, n, m);
        }
    }
    return fish;
}

reference code from: Manoj Kumar Patnaik

Key Takeaways

By optimizing the DFS traversal

• We can reduce unnecessary operations and improve clarity.
• Leveraging compact direction arrays (dr) simplifies boundary checks and movement logic.