Abstract / Summary

Find the largest group of connected fish in a grid by checking adjacent cells.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 70% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Depth First Search
• Matrix
• Union Find

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method findMaxFish that receives a two-dimensional list grid. Each cell contains a non-negative integer representing the amount of fish at that location, with zero indicating land. The algorithm traverses the grid, discovers contiguous regions of water (cells with a positive value), sums the fish in each region, and returns the maximum sum among all regions. The traversal is performed with an explicit depth-first search (DFS) using a stack, and visited cells are cleared to land after processing, which reduces the work for subsequent iterations.

Key Steps

The method begins by extracting the dimensions of the grid.

width  = len(grid[0])
height = len(grid)

A variable result is initialized to keep track of the best total found so far.

result = 0

Two nested loops iterate over every coordinate (x, y) in row-major order. When a cell containing fish is encountered, a new region exploration starts.

for y in range(height):
    for x in range(width):
        if grid[y][x] > 0:
            # start a new region

Inside the region exploration, three structures are prepared:

• caught accumulates the fish count for the current region.
• todo is a stack that holds coordinates still to be visited.
• seen records coordinates that have already been processed within this region.

caught = 0
todo = [ (x, y) ]
seen = set()

The DFS loop continues until the stack is empty. Each iteration pops a coordinate, skips it if already recorded in seen, otherwise adds it to seen and adds its fish amount to caught.

while todo:
    pos = todo.pop()
    if pos in seen:
        continue
    seen.add(pos)

    tx, ty = pos
    caught += grid[ty][tx]

Neighbouring cells are examined in the four cardinal directions. If a neighbour lies within the grid bounds and contains a positive value, it is pushed onto the stack for later processing.

if tx > 0 and grid[ty][tx - 1]:
    todo.append((tx - 1, ty))
if ty > 0 and grid[ty - 1][tx]:
    todo.append((tx, ty - 1))
if tx < width - 1  and grid[ty][tx + 1]:
    todo.append((tx + 1, ty))
if ty < height - 1 and grid[ty + 1][tx]:
    todo.append((tx, ty + 1))

When the stack empties, the total for the region (caught) is compared with the current best, and result is updated if necessary.

result = max(result, caught)

Finally, every cell recorded in seen is overwritten with zero, effectively turning the entire processed region into land. This prevents the outer loops from revisiting the same region.

for sx, sy in seen:
    grid[sy][sx] = 0

After all cells have been examined, the method returns the maximum fish count found.

return result

Edge Cases

The algorithm gracefully handles a grid that contains no water at all. In that situation the outer loops never trigger the region-exploration block, leaving result at its initial value of zero, which is then returned.

A single cell containing fish is also covered. The DFS stack starts with that cell, the neighbour checks all fail because the cell lies on the border, and the method returns the fish amount of that solitary cell.

When the grid consists of a single row or a single column, the neighbour checks correctly respect the boundary conditions (tx > 0, tx < width - 1, ty > 0, ty < height - 1). The algorithm never attempts to index outside the list, so thin grids are processed without error.

If a region touches the border of the grid, the neighbour checks that would step outside are simply omitted by the boundary guards, ensuring that only valid neighbours are considered.

Performance Optimizations

The implementation incorporates several techniques that reduce redundant work. The seen set guarantees that each coordinate inside a region is processed exactly once, even if multiple neighbours push the same coordinate onto the stack. The early continue on already-seen positions prevents unnecessary work inside the DFS loop.

After a region has been fully explored, the code overwrites every cell in that region with zero. This in-place modification means that the outer double loop will skip those cells on subsequent passes, eliminating the need for a separate visited matrix that would otherwise be consulted on each iteration.

Using a list as a stack (todo.pop()) provides constant-time push and pop operations, which is efficient for the depth-first traversal pattern employed here.

Collectively, these choices keep the amount of work proportional to the number of water cells, and the in-place clearing of processed regions prevents the algorithm from revisiting the same area multiple times.

Imagine a big pond divided into a grid of little square patches. Some of these patches have fish in them, and some are just empty water. If patches with fish are right next to each other, they form a hidden fishing hole. The goal is to visit every single square in this pond to find where the biggest group of fish friends is hiding.

The code starts by looking at the whole grid, row by row and square by square. Whenever it finds a patch with at least one fish, it knows a new adventure has begun. It starts a little list of places to look, which keeps track of all the neighboring watery squares that might also hold fish.

It travels from one patch to another, checking up, down, left, and right, to see if there are more fish nearby. As it explores, it remembers every spot it has already visited so it does not get confused and check the same place twice. It adds up all the fish found in this connected family of squares.

Once there are no more fishy neighbors to visit, it writes down how many fish were collected. Then, it clears out those spots by pretending they are land so it does not count the same fish again later. It repeats this for every part of the pond until every patch has been checked to see if it holds a secret treasure of fish. Finally, it keeps the highest number discovered during all these trips to figure out the best place to go fishing.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		C++	Python	Java			TS
	WalkCCC		C++	Python	Java
	leetcode.ca		C++	Python	Java		Go	TS
	Progiez		C++	Python	Java
github	charles-wangkai				Java
	everthis	JS
	fsq		C++
	JoshCrozier	JS
	lkwq007			Python
	Shamik07					Dart
	withaarzoo		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
Shamik07	Dart
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality