Abstract / Summary

Given a list of numbers and a target value, find two different numbers that add up to the target and return their positions.

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 58% (30+ million submissions).

Typical patterns to solve this problem:

• Array
• Hash Table

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 presented implementation solves the classic “two-sum” problem: given an integer array nums and an integer target, it returns the indices of the two distinct elements whose sum equals target. The algorithm proceeds by first creating a sorted copy of the input, then iterating through each element while using a binary search on the sorted copy to verify the existence of the required complement. When a potential complement is found, a secondary scan identifies the exact partner index, and the pair of indices is returned. If no such pair exists, an empty vector is produced.

Key Steps

Creating a sorted copy

The function begins by duplicating the original vector and sorting the duplicate. This preparation enables fast existence checks for the needed complement.

auto sorted = nums;
sort(sorted.begin(), sorted.end());

Outer iteration over the original array

A forward loop walks through each element of nums. The loop index i represents the first candidate in the potential pair.

for (int i = 0; i < nums.size(); i++)
{
    auto need = target - nums[i];
    // ...
}

Binary search for the complement

For each i, the algorithm computes the value required to reach target (need). It then performs a binary search on the sorted copy to determine whether need appears anywhere in the array. If the search fails, the loop proceeds to the next i, avoiding unnecessary work.

if (!binary_search(sorted.begin(), sorted.end(), need))
    continue;

Inner scan to locate the partner index

When the binary search confirms the presence of need, a second nested loop scans the elements that follow i (indices j > i). This scan checks the actual sum of nums[i] and nums[j]. Upon finding a matching pair, the function immediately returns the two indices as a vector.

for (int j = i+1; j < nums.size(); j++)
{
    if (nums[i] + nums[j] == target)
        return { i, j };
}

Fallback when no pair exists

If the outer loop completes without locating a valid pair, the function reaches the final statement and returns an empty vector, indicating the absence of a solution.

return {};

Edge Cases Handled

The algorithm gracefully handles inputs where the target cannot be formed by any two distinct elements. In such scenarios, the binary search will never succeed for any i, and the function will fall through to the empty-vector return.

Duplicate values in nums are accommodated because the inner scan starts from i+1, ensuring that the same element is not paired with itself while still allowing two identical numbers at different positions to be selected if they satisfy the sum condition.

Negative numbers, zero, and large positive values are all processed correctly because the arithmetic for need and the binary search operate on the full integer range without special casing.

When nums contains a single element, the outer loop runs once, the binary search may succeed if need equals that element, but the inner loop has no valid j values, leading to the eventual empty-vector return. This behavior correctly reflects the requirement for two distinct indices.

Performance Optimizations

The most notable optimization is the use of a sorted copy combined with binary search. By sorting once, the algorithm enables logarithmic-time existence checks for the complement, reducing the number of full scans required compared to a naïve double-loop approach.

The early continue after a failed binary search prevents the inner scan from executing when the complement is absent, saving work especially for large arrays where many candidates lack a matching partner.

Returning immediately upon finding a valid pair eliminates any further unnecessary iterations, ensuring that the function stops at the first solution discovered.

The choice to copy and sort the input rather than sorting the original preserves the original ordering, which is essential for returning correct indices, while still gaining the speed benefits of sorted data for the existence test.

Imagine you have a big box of numbered toy blocks and a special goal number. This code acts like a little robot helper that looks through all the blocks to find a pair that adds up to your goal. First, the robot makes a copy of all the numbers and puts them in a neat line from smallest to biggest so it can search through them really quickly.

Next, the robot starts picking up the first block and does a bit of math. It takes your goal number and subtracts the number on that first block to see what magic number it needs to find to finish the pair. It uses its fast, sorted list to check if that magic number even exists anywhere in the box. if the magic number is not there, the robot puts the first block back and moves on to the next one.

If the robot sees that the magic number is hiding somewhere, it starts looking at the other blocks one by one to find the perfect match. Once it finds the second block that makes the pair match the goal number, it remembers which spots those two blocks were sitting in and tells you exactly where they are. It is very patient and keeps trying every combination until the puzzle is solved.

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	C	Java	C#	Rust	JS	Go		TS	Ruby		Nim	PHP	Scala	Swift
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	AdelDaniel									Dart
	aylei						Rust
	begeekmyfriend			C
	BigEggStudy					C#
	black-shadows	C++
	bujosa		Python
	chandansgowda		Python
	charles-wangkai				Java
	chenyanzhe	C++
	Dijkstra-Edu			C
	DimitrisJim			C
	everthis							JS
	fartem											Ruby
	FelixFan1122					C#
	fengvyi	C++
	fsq		Python
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan				Java
	halfrost								Go
	haoel	C++
	JoshCrozier							JS
	Krazune	C++
	lennylxx			C
	linouk23	C++
	lkwq007		Python
	luangong			C							TS
	MacJim	C++
	muhammadfarhankt								Go
	pruthvikp		Python
	qiyuangong				Java
	ruoru						Rust
	Shamik07									Dart
	shreymehul					C#
	sonugiri1043	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, C++, C#, Go, Java, JavaScript, Nim, PHP, Python, Ruby, Rust, Scala, Swift, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
AdelDaniel	Dart
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	C
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fsq	Python
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C, TypeScript
MacJim	C++
muhammadfarhankt	Go
pruthvikp	Python
qiyuangong	Java
ruoru	Rust
Shamik07	Dart
shreymehul	C#
sonugiri1043	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