Abstract / Summary

Given two sorted integer arrays and an integer k, list the k smallest sum pairs formed by taking one element from each array.

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 42% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Heap (Priority Queue)

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 implementation computes the k pairs with the smallest sums from two sorted integer arrays. It builds a mapping from each possible sum to the list of pairs that generate that sum, then trims the map once the k-th smallest sum is identified, and finally extracts the required pairs in order.

Building the Sum Mapping

all = defaultdict(list)
threshold = 10**11
for i in nums1:
    if (i + nums2[0] > threshold):
        break
    for j in nums2:
        if i + j > threshold:
            break
        all[i + j].append([i, j])

The outer loop iterates over the first array, while the inner loop walks through the second array. The nested loops stop early when the current sum exceeds a large initial threshold, preventing unnecessary work for very large values.

Determining the Cut-off Sum

sums = sorted(all.keys())
size = 0
keep = True
for j in sums:
    size += len(all[j])
    if keep and size >= k:
        threshold = j
        keep = False
        continue
    if not keep:
        del all[j]

After the first pass, the keys (unique sums) are sorted. The code accumulates the count of pairs seen so far. When the cumulative count reaches k, the current sum becomes the new threshold. All larger sums are then removed from the map, shrinking the data structure to only the relevant portion.

Collecting the Result

sums = sorted(all.keys())
result = []
found = 0
for i in sums:
    for j in all[i]:
        if found == k:
            break
        result.append(j)
        found += 1

A second sorting of the remaining keys guarantees ordered traversal. The nested loops walk through each pair list, appending pairs to the result until exactly k pairs have been collected.

Edge Cases Handled

When either input list is empty, the outer or inner loop never executes, leaving the mapping empty and causing the function to return an empty list. The early-break conditions also protect against integer overflow by halting iteration once sums exceed the current threshold. If k exceeds the total number of possible pairs, the inner loop simply exhausts all entries, returning all available pairs without error.

Performance Optimizations

The algorithm avoids generating every possible pair by using two pruning mechanisms. The first uses a very high initial threshold to stop inner iteration as soon as sums become too large for the current candidate range. The second replaces the full map with a trimmed version once the k-th smallest sum is known, discarding all entries with larger sums. Sorting is performed only on the distinct sum keys, which are far fewer than the total number of pairs in many cases, reducing the overhead of ordering. The use of a defaultdict(list) enables constant-time insertion of pairs into the appropriate bucket.

Imagine you have two boxes filled with numbered blocks. One box has numbers called nums1 and the other has numbers called nums2. The goal is to pick one block from each box, add their numbers together, and find the smallest pairs you can make.

The code starts by making a collection to store the pairs based on their total sum. It uses a very large number called a threshold as a limit to make sure it does not spend too much time looking at pairs that are way too big.

It looks at every potential pair by going through the first box and then the second box. When it finds two numbers, it adds them together and puts them into a special list based on that total sum. This keeps all the pairs with the same total together in one spot.

As it finds these pairs, it checks the threshold. If the total of the pairs is getting too high, it stops looking at the larger ones to save space and keep the collection tidy.

Once all the work of grouping the pairs is finished, the code sorts the sums from smallest to largest. It goes through these sorted groups one by one and carefully collects each pair until there are exactly the number of pairs requested by k. It ignores any extra pairs that are not among the smallest ones.

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			Go
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fengvyi	C++
	fsq	C++
	halfrost							Go
	JoshCrozier			JS
	linouk23	C++
	lkwq007		Python
	luangong					TS
	lzl124631x	C++
	MacJim	C++
	qiyuangong		Python
	ruoru						Rust
	suxrobGM								C#
	varunu28				Java
	vli02									C
	wisdompeak	C++
	XiaotaoGuo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
luangong	TypeScript
lzl124631x	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++
XiaotaoGuo	C++
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