Abstract / Summary

Find the largest area formed by connected 1s in a grid of 0s and 1s.

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 74% (1+ million 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 Solution class with a method maxAreaOfIsland that receives a two-dimensional list representing a binary matrix. Cells containing 1 belong to land, while 0 denotes water. The method explores each contiguous region of land (an island) and returns the size of the largest such region. The exploration is performed with a depth-first search (DFS) that mutates the input grid to record visited cells, thereby avoiding the need for auxiliary data structures.

Core Logic

The method begins by extracting the dimensions of the grid.

m = len(grid[0])
n = len(grid)

m holds the number of columns, and n holds the number of rows.

A nested helper function count implements the recursive DFS. It receives the column index x and the row index y. The first guard checks whether the current cell is land; if it is water, the recursion terminates with a contribution of zero.

def count(x, y):
    if grid[y][x] != 1:
        return 0

When a land cell is encountered, it is immediately marked with the sentinel value 2. This in-place marking guarantees that the same cell will never be processed again during the current or any subsequent island traversal.

    grid[y][x] = 2  # avoid processing the same island multiple times

The area contributed by the current cell starts at one. The function then recursively visits the four orthogonal neighbours, respecting the grid boundaries. Each recursive call returns the area of the sub-island reachable from that neighbour, and the results are accumulated.

    area = 1
    if x > 0:
        area += count(x - 1, y)
    if x < m - 1:
        area += count(x + 1, y)
    if y > 0:
        area += count(x, y - 1)
    if y < n - 1:
        area += count(x, y + 1)
    return area

The outer loops iterate over every cell in row-major order. When an unvisited land cell (grid[y][x] == 1) is found, the count function is invoked, and its returned area is compared with the current maximum.

result = 0
for y in range(n):
    for x in range(m):
        if grid[y][x] == 1:
            result = max(result, count(x, y))
return result

The final value of result is the size of the largest island discovered.

Edge Cases Handled

The algorithm correctly processes islands that touch the grid borders because the boundary checks (x > 0, x < m - 1, y > 0, y < n - 1) prevent out-of-range accesses while still allowing recursion into edge cells.

A single isolated land cell is treated as an island of area one; the recursion immediately returns after marking the cell, and the outer loop records the area.

When the grid contains only water (0 everywhere), the condition grid[y][x] == 1 never holds, leaving result at its initial value of zero, which is the correct maximum area.

If the entire grid is land, the DFS will traverse the whole matrix in a single recursive cascade, marking every cell as visited and returning the total number of cells as the area.

The implementation assumes that the input grid has at least one row and one column, which aligns with the problem constraints. The dimension extraction (len(grid[0])) safely accesses the first row because of this guarantee.

Performance Optimizations

The most notable optimization is the in-place marking of visited cells by overwriting land (1) with the sentinel value 2. This eliminates the need for an auxiliary boolean matrix or a set to track visited positions, thereby reducing memory overhead.

By performing the DFS directly from each unvisited land cell, the algorithm ensures that each cell is visited exactly once. The recursive calls propagate only through contiguous land, so the total number of recursive invocations equals the number of land cells.

The use of the built-in max function to update the running maximum avoids additional conditional branching. The outer loops scan the grid in a straightforward linear fashion, and the early exit from the count function when encountering water prevents unnecessary recursion into non-land regions.

Overall, the combination of in-place state mutation and a single pass over the grid yields an efficient solution that scales linearly with the size of the input matrix.

Imagine this grid is a big blue ocean filled with little square islands. Some squares are water, and some squares are land. The goal is to find the biggest island out of all of them by counting how many land squares are touching each other.

The code starts by walking through every single square on the map, looking for a piece of land. Once it finds a land square, it starts a special search to see how far that island goes. It looks up, down, left, and right to find neighbors. Every time it finds a new piece of land, it paints that square a different color so it knows it already visited it. It keeps adding up all the connected pieces it finds until there are no more neighbors to look at.

After it counts all the pieces of one whole island, it remembers how big that island was. Then it keeps looking through the rest of the map to see if there are any other islands to count. If it finds another island that is even bigger than the one it counted before, it keeps that new, bigger number instead. By the time it finishes checking every single square on the map, it knows exactly how big the biggest island is.

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++	Java	Python					TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python			Rust	Go	TS
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy				C#
	black-shadows	C++
	bujosa			Python
	charles-wangkai		Java
	everthis					JS
	fengvyi	C++
	gouthampradhan		Java
	halfrost							Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	Krazune	C++
	lkwq007			Python
	qiyuangong		Java
	ruoru						Rust
	shreymehul				C#
	suxrobGM				C#
	varunu28		Java
	vthwang		Java
	YuriSpiridonov			Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lkwq007	Python
qiyuangong	Java
ruoru	Rust
shreymehul	C#
suxrobGM	C#
varunu28	Java
vthwang	Java
YuriSpiridonov	Python
zfang399	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