2658. Maximum Number of Fish in a Grid
Approach
DFS flood fill each unvisited water cell accumulating fish count; return global max.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.
BFS explores nodes level by level, guaranteeing the shortest path in unweighted graphs. Use a Queue<T> and a visited set. Classic applications: shortest path, level-order tree traversal, multi-source distance (e.g., "01 matrix"), and word ladder transformations.
// Approach: DFS flood fill each unvisited water cell accumulating fish count; return global max.
// Time: O(mn) Space: O(mn)
public class Solution
{
public int FindMaxFish(int[][] grid)
{
int ans = 0;
for (int i = 0; i < grid.Length; i++)
{
for (int j = 0; j < grid[i].Length; j++)
{
if (grid[i][j] > 0)
ans = Math.Max(ans, dfs(i, j, grid));
}
}
return ans;
}
private int dfs(int i, int j, int[][] grid)
{
if (i < 0 || i == grid.Length || j < 0 || j == grid[0].Length)
return 0;
if (grid[i][j] == 0)
return 0;
int fish = grid[i][j];
grid[i][j] = 0;
int sum = 0;
sum += fish;
sum += dfs(i, j + 1, grid);
sum += dfs(i, j - 1, grid);
sum += dfs(i + 1, j, grid);
sum += dfs(i - 1, j, grid);
return sum;
}
}