Skip to content
LEETFLIX

Maximum Number of Fish in a Grid

MediumArrayDFSBFSMatrix
Solve on LeetCode

Medium · graph / tree walk solution for Maximum Number of Fish in a Grid. Python, Go, and a step-by-step animation.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 2658. Maximum Number of Fish in a Grid. The copyrighted prompt is on LeetCode. This page is a working graph / tree walk solution for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

  • —Player inputs are capped so the animation stays readable.
  • —Match LeetCode's own constraints when you submit there.

Examples

Input

grid =
[110,010,001]

Output

2

Two islands: the connected 1s in the top-left, and the lone 1 at the bottom.

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

Maximum Number of Fish in a Grid — graph / tree walk

Each unvisited land cell starts an island; BFS paints the whole component. Built for LeetCode 2658. Maximum Number of Fish in a Grid.

A grid / graph walk is the same idea on trees, mazes and adjacency lists: mark what you touch so you never count it twice, and expand to neighbours.

Algorithm

  1. Scan every cell.
  2. On an unvisited '1', increment the count and BFS-paint the island to '0'.
Time
O(mn)
Space
O(mn)
Solution.py
class Solution:    def maximumNumberOfFishInAGrid(self, grid: list[str]) -> int:        if not grid:            return 0        rows, cols = len(grid), len(grid[0])        g = [list(row) for row in grid]        islands = 0         def flood(sr: int, sc: int) -> None:            q = [(sr, sc)]            g[sr][sc] = "0"            while q:                r, c = q.pop(0)                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):                    nr, nc = r + dr, c + dc                    if 0 <= nr < rows and 0 <= nc < cols and g[nr][nc] == "1":                        g[nr][nc] = "0"                        q.append((nr, nc))         for r in range(rows):            for c in range(cols):                if g[r][c] == "1":                    islands += 1                    flood(r, c)        return islands
Watch this run

03

Interactive walkthrough

Playing “Maximum Number of Fish in a Grid — graph / tree walk”. Edit the input, hit Run, then scrub.

Approach: Maximum Number of Fish in a Grid — graph / tree walk

Loading animation…