Abstract / Summary

Determine if a target value exists within a sorted two-dimensional matrix by searching its rows and columns efficiently.

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 54% (5+ million submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Matrix

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 solves the classic “search a value in a 2-D matrix” problem. It treats each row as an independent sorted array and iterates through the rows to locate the one that could contain the target. Once a candidate row is found, it delegates the actual lookup to the standard library’s binary search routine. The algorithm returns a boolean indicating whether the target exists in the matrix.

Key Steps

Row-wise filtering

for (auto& r : matrix)
{
    if (target < r.front())
        return false;
    if (target > r.back())
        continue;

The loop walks through each row r. The first conditional checks whether the target is smaller than the smallest element of the current row (r.front()). Because rows are sorted in ascending order, a smaller target cannot appear in any later row, so the function returns false immediately. The second conditional discards rows whose largest element (r.back()) is still smaller than the target, allowing the loop to continue to the next row.

Binary search within the candidate row

    return binary_search(r.begin(), r.end(), target);
}

When the target lies between the first and last elements of a row, the code invokes std::binary_search. This standard algorithm performs a logarithmic search over the row’s range, yielding a true result if the target is present and false otherwise. The return statement exits the function as soon as the appropriate row has been examined.

Exhaustive failure case

return false;

If the loop finishes without finding a suitable row (for example, when the matrix is empty or all rows are exhausted), the function reaches this final statement and reports that the target is absent.

Edge Cases Handled

When the matrix contains no rows, the range-based for loop executes zero times, and the function falls through to the final return false;. This correctly reports that no element can be found in an empty structure.

If a row itself is empty, calling r.front() or r.back() would be undefined. The code assumes that every row contains at least one element, which aligns with the typical problem constraints where each sub-vector is non-empty.

The early-exit condition if (target < r.front()) return false; also covers the scenario where the target is smaller than every element in the matrix. Because rows are processed in order, the first row’s smallest element provides a global lower bound; encountering a smaller target triggers an immediate false without scanning the remaining rows.

Conversely, when the target exceeds the largest element of the last row, the loop iterates through all rows, each time hitting if (target > r.back()) continue;. After the loop ends, the final return false; correctly indicates the target’s absence.

Performance Optimizations

The algorithm leverages two natural ordering properties of the matrix: each row is sorted, and rows themselves are ordered by their first elements. By checking the front and back values of each row before invoking a full search, the code eliminates unnecessary binary searches on rows that cannot possibly contain the target. This reduces the number of expensive logarithmic operations to at most one per execution.

Using std::binary_search provides a highly tuned implementation that benefits from in-line optimizations and branch prediction friendly code paths, ensuring the inner search runs efficiently.

The early termination when target < r.front() prevents the algorithm from traversing the remainder of the matrix once it is clear that the target cannot appear later, saving time especially for large matrices where the target is smaller than the global minimum.

Overall, the combination of row-level bounds checking and a single binary search yields a solution that scales well with both the number of rows and the length of each row, while keeping the code concise and leveraging the standard library for optimal low-level performance.

Imagine you have a big box filled with smaller boxes, and each one of those smaller boxes is packed with numbers that are all lined up neatly from smallest to largest. You are trying to find one specific secret number hidden somewhere deep inside. This code starts by looking at each little box one by one. First, it checks the very first number in the box to see if the secret number is too small to be hiding there. Then, it checks the very last number in the box to see if the secret number is too big to be hiding there. If the secret number fits somewhere between those two spots, the code stops looking at the outside of the boxes and starts searching very quickly inside that specific one to find your secret number. If it finds it, you know it is there. If it checks every little box and still has not found the secret number, then the number just is not in the big box at all.

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

not analyzed yet

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		Rust		JS			Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei					Rust
	begeekmyfriend				C
	BigEggStudy						C#
	black-shadows	C++
	bujosa					Rust
	charles-wangkai			Java
	chenyanzhe	C++
	DimitrisJim				C
	everthis							JS
	fartem								Ruby
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost										Go
	JoshCrozier							JS
	keineahnung2345	C++
	lennylxx				C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	ruoru					Rust
	shreymehul						C#
	suxrobGM						C#
	trung-hn		Python
	varunu28			Java
	vli02				C
	vthwang			Java
	XiaotaoGuo	C++
	yuanliu666									Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
yuanliu666	Kotlin
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