2658. Maximum Number of Fish in a Grid Solution

The problem

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

A land cell if grid[r][c] = 0, or
A water cell containing grid[r][c] fish, if grid[r][c] > 0.

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

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

Return the maximum number of fish the fisher can catch if he chooses his starting cell optimally, or 0 if no water cell exists.

An adjacent cell of the cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) or (r - 1, c) if it exists.

Example 1:

Input: grid = [[0,2,1,0],[4,0,0,3],[1,0,0,4],[0,3,2,0]]
Output: 7
Explanation: The fisher can start at cell (1,3) and collect 3 fish, then move to cell (2,3) and collect 4 fish.

Example 2:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
Output: 1
Explanation: The fisher can start at cells (0,0) or (3,3) and collect a single fish.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10
0 <= grid[i][j] <= 10

Approach overview

Problem Overview: You are given a 2D grid where each cell contains some fish. A value of 0 represents land, while positive numbers represent water cells containing fish. Starting from any water cell, you can move up, down, left, or right and collect all fish from that connected region. The task is to compute the maximum total fish you can collect from a single connected component.

Approach 1: Depth-First Search (DFS) Traversal (Time: O(m*n), Space: O(m*n))

This approach treats the grid as a graph where each water cell is a node connected to its four directional neighbors. Iterate through every cell in the matrix. When you encounter a cell with fish (grid[r][c] > 0), start a Depth-First Search to explore the entire connected component. During the DFS, accumulate the fish count and mark cells as visited (commonly by setting them to 0 or tracking them in a visited set). Each DFS call walks through all reachable water cells, ensuring every component is processed exactly once. This approach works well because DFS naturally explores entire regions before returning.

Approach 2: Breadth-First Search (BFS) Traversal (Time: O(m*n), Space: O(m*n))

The BFS solution follows the same connected-component idea but uses a queue instead of recursion. When you find a water cell, push it into a queue and start a Breadth-First Search. Repeatedly pop cells from the queue, add their fish count to the running total, and push valid neighboring cells that contain fish. Mark visited cells immediately to avoid revisiting them. BFS explores the region level by level and guarantees each grid cell is processed once. The logic is almost identical to DFS, but BFS avoids recursion depth issues in very large grids.

Approach 3: Union-Find (Disjoint Set) (Time: O(m*n α(n)), Space: O(m*n))

Another way to model the problem is by grouping adjacent water cells using Union Find. Each cell is treated as a node in a disjoint set. When two neighboring cells contain fish, union their sets and maintain a running sum of fish for each component. After processing the entire matrix, scan the component sums and return the maximum. While slightly more complex to implement, this approach generalizes well to problems that require repeated connectivity queries.

Recommended for interviews: DFS or BFS traversal. Interviewers expect you to recognize the grid as a connected-component problem and apply a graph traversal. DFS is usually the fastest to implement, while BFS is equally optimal. Union-Find demonstrates deeper graph modeling but is rarely necessary unless the problem involves dynamic connectivity.

Approach 1: Depth-First Search (DFS)

This approach involves treating the grid as a graph and using depth-first search to explore each connected component of water cells. The goal is to aggregate the number of fish in each connected component and return the maximum number encountered. We start from each unvisited water cell and attempt to explore the maximum number of fish that can be collected from that starting point using DFS.

Python

def dfs(grid, visited, r, c):
    if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == 0 or visited[r][c]:
        return 0
    visited[r][c] = True
    fish_count = grid[r][c]
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    for dr, dc in directions:
        fish_count += dfs(grid, visited, r + dr, c + dc)
    return fish_count

def max_fish(grid):
    m, n = len(grid), len(grid[0])
    visited = [[False] * n for _ in range(m)]
    max_fish = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] > 0 and not visited[r][c]:
                fish_count = dfs(grid, visited, r, c)
                max_fish = max(max_fish, fish_count)
    return max_fish

# Example Usage
if __name__ == "__main__":
    grid = [[0, 2, 1, 0], [4, 0, 0, 3], [1, 0, 0, 4], [0, 3, 2, 0]]
    print("Maximum number of fish:", max_fish(grid))

Java

import java.util.*;

public class MaxFish {
    private static int dfs(int[][] grid, boolean[][] visited, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0 || visited[r][c])
            return 0;
        
        visited[r][c] = true;
        int fishCount = grid[r][c];
        
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int[] dir : directions) {
            fishCount += dfs(grid, visited, r + dir[0], c + dir[1]);
        }
        return fishCount;
    }
    
    public static int maxFish(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int maxFish = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0 && !visited[i][j]) {
                    int fishCount = dfs(grid, visited, i, j);
                    maxFish = Math.max(maxFish, fishCount);
                }
            }
        }
        return maxFish;
    }
    
    public static void main(String[] args) {
        int[][] grid = {{0, 2, 1, 0}, {4, 0, 0, 3}, {1, 0, 0, 4}, {0, 3, 2, 0}};
        System.out.println("Maximum number of fish: " + maxFish(grid));
    }
}

C++

#include <vector>
#include <iostream>
using namespace std;

int dfs(const vector<vector<int>>& grid, vector<vector<bool>>& visited, int r, int c) {
    if (r < 0 || r >= grid.size() || c < 0 || c >= grid[0].size() || grid[r][c] == 0 || visited[r][c])
        return 0;
    
    visited[r][c] = true;
    int fish_count = grid[r][c];
    
    vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    for (auto& dir : directions) {
        fish_count += dfs(grid, visited, r + dir.first, c + dir.second);
    }
    return fish_count;
}

int maxFish(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    int max_fish = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] > 0 && !visited[i][j]) {
                int fish_count = dfs(grid, visited, i, j);
                max_fish = max(max_fish, fish_count);
            }
        }
    }
    return max_fish;
}

int main() {
    vector<vector<int>> grid = {{0, 2, 1, 0}, {4, 0, 0, 3}, {1, 0, 0, 4}, {0, 3, 2, 0}};
    cout << "Maximum number of fish: " << maxFish(grid) << endl;
    return 0;
}

JavaScript

function dfs(grid, visited, r, c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] === 0 || visited[r][c])
        return 0;
    
    visited[r][c] = true;
    let fishCount = grid[r][c];
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    for (let [dr, dc] of directions) {
        fishCount += dfs(grid, visited, r + dr, c + dc);
    }
    return fishCount;
}

function maxFish(grid) {
    const m = grid.length, n = grid[0].length;
    const visited = Array.from(Array(m), () => Array(n).fill(false));
    let maxFish = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] > 0 && !visited[i][j]) {
                const fishCount = dfs(grid, visited, i, j);
                maxFish = Math.max(maxFish, fishCount);
            }
        }
    }
    return maxFish;
}

// Example Usage
const grid = [[0, 2, 1, 0], [4, 0, 0, 3], [1, 0, 0, 4], [0, 3, 2, 0]];
console.log("Maximum number of fish: " + maxFish(grid));

#include <stdio.h>

#define MAX 10

int dfs(int grid[MAX][MAX], int m, int n, int visited[MAX][MAX], int r, int c) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0 || visited[r][c])
        return 0;
    
    visited[r][c] = 1;
    int fish_count = grid[r][c];
    
    int directions[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    for (int i = 0; i < 4; i++) {
        int new_r = r + directions[i][0], new_c = c + directions[i][1];
        fish_count += dfs(grid, m, n, visited, new_r, new_c);
    }
    return fish_count;
}

int maxFish(int grid[MAX][MAX], int m, int n) {
    int visited[MAX][MAX] = {0};
    int max_fish = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] > 0 && !visited[i][j]) {
                int fish_count = dfs(grid, m, n, visited, i, j);
                if (fish_count > max_fish) max_fish = fish_count;
            }
        }
    }
    return max_fish;
}

int main() {
    int grid[4][4] = {{0, 2, 1, 0}, {4, 0, 0, 3}, {1, 0, 0, 4}, {0, 3, 2, 0}};
    printf("Maximum number of fish: %d\n", maxFish(grid, 4, 4));
    return 0;
}

using System;

class MaxFish {
    private static int DFS(int[,] grid, bool[,] visited, int r, int c) {
        int m = grid.GetLength(0), n = grid.GetLength(1);
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r,c] == 0 || visited[r,c])
            return 0;
        
        visited[r,c] = true;
        int fishCount = grid[r,c];
        
        int[][] directions = {new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[] {-1, 0}};
        foreach (var dir in directions) {
            fishCount += DFS(grid, visited, r + dir[0], c + dir[1]);
        }
        return fishCount;
    }
    
    public static int MaxFish(int[,] grid) {
        int m = grid.GetLength(0);
        int n = grid.GetLength(1);
        bool[,] visited = new bool[m, n];
        int maxFish = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i, j] > 0 && !visited[i, j]) {
                    int fishCount = DFS(grid, visited, i, j);
                    maxFish = Math.Max(maxFish, fishCount);
                }
            }
        }
        return maxFish;
    }

    static void Main() {
        int[,] grid = {{0, 2, 1, 0}, {4, 0, 0, 3}, {1, 0, 0, 4}, {0, 3, 2, 0}};
        Console.WriteLine("Maximum number of fish: " + MaxFish(grid));
    }
}

The Python code leverages DFS for traversing each water connected component. The dfs function accesses adjacent cells recursively, summing up the fish counts. The max_fish function iterates through the grid, utilizing dfs whenever an unvisited water cell is found, updating the best possible fish collection count.

Complexity

Time Complexity: O(m*n), every cell is assessed in a single DFS walk.

Space Complexity: O(m*n), due to recursion depth and visited status storage.

Try this approach in the editor

Approach 2: Breadth-First Search (BFS)

This alternative approach uses breadth-first search to traverse each component of water cells in the grid. Instead of exploring depth-first, it explores all neighbor cells at the present "depth" before moving deeper. The total number of fish for each component is counted, with the goal of finding the maximum possible collection.

Python

from collections import deque

def bfs(grid, visited, r, c):
    queue = deque([(r, c)])
    visited[r][c] = True
    fish_count = 0
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    while queue:
        r, c = queue.popleft()
        fish_count += grid[r][c]
        for dr, dc in directions:
            new_r, new_c = r + dr, c + dc
            if 0 <= new_r < len(grid) and 0 <= new_c < len(grid[0]) and grid[new_r][new_c] > 0 and not visited[new_r][new_c]:
                visited[new_r][new_c] = True
                queue.append((new_r, new_c))
    return fish_count

def max_fish(grid):
    m, n = len(grid), len(grid[0])
    visited = [[False] * n for _ in range(m)]
    max_fish = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] > 0 and not visited[r][c]:
                fish_count = bfs(grid, visited, r, c)
                max_fish = max(max_fish, fish_count)
    return max_fish

# Example Usage
if __name__ == "__main__":
    grid = [[0, 2, 1, 0], [4, 0, 0, 3], [1, 0, 0, 4], [0, 3, 2, 0]]
    print("Maximum number of fish:", max_fish(grid))

Java

import java.util.*;

public class MaxFishBFS {
    private static int bfs(int[][] grid, boolean[][] visited, int startR, int startC) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{startR, startC});
        visited[startR][startC] = true;
        
        int fishCount = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            int r = point[0], c = point[1];
            fishCount += grid[r][c];
            for (int[] dir : directions) {
                int newR = r + dir[0], newC = c + dir[1];
                if (newR >= 0 && newR < grid.length && newC >= 0 && newC < grid[0].length &&
                    !visited[newR][newC] && grid[newR][newC] > 0) {
                    visited[newR][newC] = true;
                    queue.offer(new int[]{newR, newC});
                }
            }
        }
        return fishCount;
    }

    public static int maxFish(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int maxFish = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0 && !visited[i][j]) {
                    int fishCount = bfs(grid, visited, i, j);
                    maxFish = Math.max(maxFish, fishCount);
                }
            }
        }
        return maxFish;
    }

    public static void main(String[] args) {
        int[][] grid = {{0, 2, 1, 0}, {4, 0, 0, 3}, {1, 0, 0, 4}, {0, 3, 2, 0}};
        System.out.println("Maximum number of fish: " + maxFish(grid));
    }
}

C++

#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int startR, int startC) {
    queue<pair<int, int>> q;
    q.push({startR, startC});
    visited[startR][startC] = true;
    
    int fishCount = 0;
    vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        fishCount += grid[r][c];
        for (auto& dir : directions) {
            int newR = r + dir.first, newC = c + dir.second;
            if (newR >= 0 && newR < grid.size() && newC >= 0 && newC < grid[0].size() && 
                !visited[newR][newC] && grid[newR][newC] > 0) {
                visited[newR][newC] = true;
                q.push({newR, newC});
            }
        }
    }
    return fishCount;
}

int maxFish(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<bool>> visited(m, vector<bool>(n, false));
    int maxFish = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] > 0 && !visited[i][j]) {
                int fishCount = bfs(grid, visited, i, j);
                maxFish = max(maxFish, fishCount);
            }
        }
    }
    return maxFish;
}

int main() {
    vector<vector<int>> grid = {{0, 2, 1, 0}, {4, 0, 0, 3}, {1, 0, 0, 4}, {0, 3, 2, 0}};
    cout << "Maximum number of fish: " << maxFish(grid) << endl;
    return 0;
}

JavaScript

function bfs(grid, visited, r, c) {
    const queue = [[r, c]];
    visited[r][c] = true;
    let fishCount = 0;
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];

    while (queue.length > 0) {
        const [r, c] = queue.shift();
        fishCount += grid[r][c];
        for (const [dr, dc] of directions) {
            const newR = r + dr, newC = c + dc;
            if (newR >= 0 && newR < grid.length && newC >= 0 && newC < grid[0].length &&
                grid[newR][newC] > 0 && !visited[newR][newC]) {
                visited[newR][newC] = true;
                queue.push([newR, newC]);
            }
        }
    }
    return fishCount;
}

function maxFish(grid) {
    const m = grid.length, n = grid[0].length;
    const visited = Array.from({ length: m }, () => Array(n).fill(false));
    let maxFish = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] > 0 && !visited[r][c]) {
                const fishCount = bfs(grid, visited, r, c);
                maxFish = Math.max(maxFish, fishCount);
            }
        }
    }
    return maxFish;
}

// Example Usage
const grid = [[0, 2, 1, 0], [4, 0, 0, 3], [1, 0, 0, 4], [0, 3, 2, 0]];
console.log("Maximum number of fish: " + maxFish(grid));

#include <stdio.h>
#include <stdbool.h>

#define MAX 10

typedef struct { int r, c; } Point;

int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int bfs(int grid[MAX][MAX], int m, int n, bool visited[MAX][MAX], int startR, int startC) {
    Point queue[MAX * MAX];
    int front = 0, rear = 0;
    
    queue[rear++] = (Point){startR, startC};
    visited[startR][startC] = true;
    
    int fish_count = grid[startR][startC];
    
    while (front < rear) {
        Point p = queue[front++];
        for(int i = 0; i < 4; ++i) {
            int newR = p.r + directions[i][0], newC = p.c + directions[i][1];
            if (newR >= 0 && newR < m && newC >= 0 && newC < n && !visited[newR][newC] && grid[newR][newC] > 0) {
                visited[newR][newC] = true;
                fish_count += grid[newR][newC];
                queue[rear++] = (Point){newR, newC};
            }
        }
    }
    return fish_count;
}

int maxFish(int grid[MAX][MAX], int m, int n) {
    bool visited[MAX][MAX] = {false};
    int max_fish = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] > 0 && !visited[i][j]) {
                int fish_count = bfs(grid, m, n, visited, i, j);
                if (fish_count > max_fish) max_fish = fish_count;
            }
        }
    }
    return max_fish;
}

int main() {
    int grid[4][4] = {{0, 2, 1, 0}, {4, 0, 0, 3}, {1, 0, 0, 4}, {0, 3, 2, 0}};
    printf("Maximum number of fish: %d\n", maxFish(grid, 4, 4));
    return 0;
}

using System;
using System.Collections.Generic;

class MaxFishBFS {
    private static int BFS(int[,] grid, bool[,] visited, int startR, int startC) {
        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((startR, startC));
        visited[startR, startC] = true;

        int fishCount = 0;
        int[,] directions = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

        while (queue.Count > 0) {
            var (r, c) = queue.Dequeue();
            fishCount += grid[r, c];
            for (int i = 0; i < directions.GetLength(0); i++) {
                int newR = r + directions[i, 0], newC = c + directions[i, 1];
                if (newR >= 0 && newR < grid.GetLength(0) && newC >= 0 && newC < grid.GetLength(1) &&
                    !visited[newR, newC] && grid[newR, newC] > 0) {
                    visited[newR, newC] = true;
                    queue.Enqueue((newR, newC));
                }
            }
        }
        return fishCount;
    }

    public static int MaxFish(int[,] grid) {
        int m = grid.GetLength(0);
        int n = grid.GetLength(1);
        bool[,] visited = new bool[m, n];
        int maxFish = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i, j] > 0 && !visited[i, j]) {
                    int fishCount = BFS(grid, visited, i, j);
                    maxFish = Math.Max(maxFish, fishCount);
                }
            }
        }
        return maxFish;
    }

    static void Main() {
        int[,] grid = {{0, 2, 1, 0}, {4, 0, 0, 3}, {1, 0, 0, 4}, {0, 3, 2, 0}};
        Console.WriteLine("Maximum number of fish: " + MaxFish(grid));
    }
}

This Python solution accomplishes BFS exploration using deque from the collections module for queue management. It iterates through each cell's neighbors breadth-first, updating the maximum fish collection for each connected water region.

Complexity

Time Complexity: O(m*n) because each matrix cell is processed once maximally.

Space Complexity: O(m*n) is required by the queue and visitation markers.

Try this approach in the editor

Approach 3: DFS

According to the problem description, we only need to find the number of fish in each connected water area and then take the maximum value. Therefore, we can use the depth-first search method to solve this problem.

We define a function dfs(i, j), which indicates the maximum number of fish that can be caught starting from the cell in the i-th row and the j-th column. The execution logic of the function dfs(i, j) is as follows:

We use a variable cnt to record the number of fish in the current cell, and then set the number of fish in the current cell to 0, indicating that it has been fished. Then we traverse the four directions of the current cell, if the cell (x, y) in a certain direction is in the grid and is a water cell, then we recursively call the dfs(x, y) function and add the return value to cnt. Finally, return cnt.

In the main function, we traverse all the cells (i, j). If the current cell is a water cell, we call the dfs(i, j) function, take the maximum value of the return value as the answer, and return it.

The time complexity is O(m times n), and the space complexity is O(m times n). where m and n are the number of rows and columns of the grid graph respectively.

TypeScript

function findMaxFish(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;

    const dirs = [-1, 0, 1, 0, -1];
    const dfs = (i: number, j: number): number => {
        let cnt = grid[i][j];
        grid[i][j] = 0;
        for (let k = 0; k < 4; ++k) {
            const x = i + dirs[k];
            const y = j + dirs[k + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {
                cnt += dfs(x, y);
            }
        }
        return cnt;
    };

    let ans = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] > 0) {
                ans = Math.max(ans, dfs(i, j));
            }
        }
    }
    return ans;
}

func findMaxFish(grid [][]int) (ans int) {
	m, n := len(grid), len(grid[0])
	dirs := [5]int{-1, 0, 1, 0, -1}
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		cnt := grid[i][j]
		grid[i][j] = 0
		for k := 0; k < 4; k++ {
			x, y := i+dirs[k], j+dirs[k+1]
			if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0 {
				cnt += dfs(x, y)
			}
		}
		return cnt
	}
	for i := range grid {
		for j := range grid[i] {
			if grid[i][j] > 0 {
				ans = max(ans, dfs(i, j))
			}
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Depth-First Search (DFS)	Time Complexity: O(mn), every cell is assessed in a single DFS walk. Space Complexity: O(mn), due to recursion depth and visited status storage.
Breadth-First Search (BFS)	Time Complexity: O(mn) because each matrix cell is processed once maximally. Space Complexity: O(mn) is required by the queue and visitation markers.
DFS	–

Approach

Complexity

Depth-First Search (DFS)

Time Complexity: O(m*n), every cell is assessed in a single DFS walk.

Space Complexity: O(m*n), due to recursion depth and visited status storage.

Breadth-First Search (BFS)

Time Complexity: O(m*n) because each matrix cell is processed once maximally.

Space Complexity: O(m*n) is required by the queue and visitation markers.

DFS

–

Complexity analysis

Approach	Time	Space	When to Use
Depth-First Search (DFS)	O(m*n)	O(m*n)	Most common interview solution. Simple recursive traversal for connected components.
Breadth-First Search (BFS)	O(m*n)	O(m*n)	Preferred when avoiding recursion or handling very large grids.
Union-Find (Disjoint Set)	O(m*n α(n))	O(m*n)	Useful when modeling connectivity across multiple queries or dynamic merges.

Frequently asked questions

Is Maximum Number of Fish in a Grid easy or hard?

The problem is rated Medium on LeetCode with an acceptance rate around 70%. The core idea is straightforward if you recognize it as a connected-component traversal in a grid. Candidates comfortable with DFS/BFS on matrices usually solve it quickly.

Maximum Number of Fish in a Grid Python/Java solution

Most implementations use DFS or BFS traversal. In Python, recursion or a deque-based BFS is common. In Java or C++, iterative BFS with a queue is frequently used. All versions follow the same logic: explore a connected water region, sum fish values, and track the maximum component sum.

How to solve Maximum Number of Fish in a Grid in O(n)?

Treat the grid as a graph and compute the sum of each connected component using DFS or BFS. Iterate through every cell and start a traversal whenever a positive fish count is found. Mark visited cells to avoid duplicate work. Since each cell is processed once, the runtime is O(m*n).

What is the best approach for Maximum Number of Fish in a Grid?

Depth-First Search (DFS) or Breadth-First Search (BFS) is the best approach. The grid can be treated as a graph where each water cell connects to its four neighbors. Traversing each connected component and summing the fish gives the result. Both approaches run in O(m*n) time and process each cell once.

Is Maximum Number of Fish in a Grid asked at Google/Amazon/Meta?

Grid traversal and connected component problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving islands, regions, or matrix exploration are common. This problem tests graph traversal, matrix handling, and basic DFS/BFS implementation.

What data structure is used in Maximum Number of Fish in a Grid?

The primary data structures are recursion stack for DFS or a queue for BFS. The grid itself acts as the graph representation. Some implementations also use a visited set or modify the grid in place to mark visited cells.

What is the time complexity of Maximum Number of Fish in a Grid?

The optimal time complexity is O(m*n), where m and n are the grid dimensions. Each cell is visited at most once during DFS or BFS traversal while exploring connected water regions. Space complexity is also O(m*n) in the worst case due to recursion stack or queue usage.

Maximum Number of Fish in a Grid solution and explanation

The problem

Approach overview

Approach 1: Depth-First Search (DFS)

Approach 2: Breadth-First Search (BFS)

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Number of Fish in a Grid solution and explanation

The problem

Approach overview

Approach 1: Depth-First Search (DFS)

Approach 2: Breadth-First Search (BFS)

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems