Find K Pairs with Smallest Sums — Problem & Solution
Find K Pairs with Smallest Sums solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find K Pairs with Smallest Sums is a medium coding problem on arrays and heap, asked in Amazon, Google, LinkedIn and Hotstar interviews.
- Difficulty: Medium
- Topics: Arrays, Heap
- Asked at: Amazon, Google, LinkedIn, Hotstar
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Two arrays sorted in non-decreasing order are given. A pair [u, v] takes one number from each.
Return the k pairs with the smallest sums, ordered by sum ascending; ties are broken by the smaller u, then the smaller v. If fewer than k pairs exist, return all of them.
Example 1
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Example 2
Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: Both 1s in `nums1` pair with the 1 in `nums2`.
Example 3
Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [[1,3],[2,3]]
Explanation: Only two pairs exist.
Constraints
1 <= nums1.length, nums2.length <= 1000-10^9 <= nums1[i], nums2[i] <= 10^9nums1 and nums2 are sorted in non-decreasing order.1 <= k <= 1000The pairs are returned sorted by sum, then by u, then by v.
Hints for Find K Pairs with Smallest Sums
Hint 1
Building all
n × mpairs is far too many.Hint 2
For a fixed
i, the sumsnums1[i] + nums2[j]increase withj, so only the frontier matters.Hint 3
Seed a min-heap with
[i, 0]for eachi, and on popping[i, j]push[i, j + 1].
How to solve Find K Pairs with Smallest Sums
Keep a frontier of candidate pairs in a min-heap. Both arrays are sorted, so the next-smallest pair is always one step to the right of a pair already taken.
Approach
- Push
[i, 0]for the firstmin(n, k)rows — no more can ever be needed. - Pop the smallest, record
[nums1[i], nums2[j]]. - Push
[i, j + 1]if that column exists. - Stop after
kpops or when the heap empties.
Why it works
Only min(n, k) rows need seeding, because the answer can hold at most k pairs and each row contributes its smallest first. Ordering the heap on (sum, u, v) rather than the sum alone is what makes the output deterministic — without it, equal sums could come out in any order and two correct implementations would disagree.
Complexity
- Time —
O(k log k) - Space —
O(k)
Pitfalls
- Seeding every row is wasteful when
nfar exceedsk. - Pushing both
[i+1, j]and[i, j+1]duplicates pairs unless visits are tracked. - Fewer than
kpairs may exist; the loop must also stop on an empty heap.
Reference solution
Python
from typing import List
import heapq
def kSmallestPairs(nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
n, m = len(nums1), len(nums2)
heap = []
for i in range(min(n, k)):
heapq.heappush(heap, (nums1[i] + nums2[0], nums1[i], nums2[0], i, 0))
out = []
while len(out) < k and heap:
_, u, v, i, j = heapq.heappop(heap)
out.append([u, v])
if j + 1 < m:
heapq.heappush(heap, (nums1[i] + nums2[j + 1], nums1[i], nums2[j + 1], i, j + 1))
return outJava
public static int[][] kSmallestPairs(int[] nums1, int[] nums2, int k) {
int n = nums1.length, m = nums2.length;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> {
long sa = (long) nums1[a[0]] + nums2[a[1]];
long sb = (long) nums1[b[0]] + nums2[b[1]];
if (sa != sb) return Long.compare(sa, sb);
if (nums1[a[0]] != nums1[b[0]]) return Integer.compare(nums1[a[0]], nums1[b[0]]);
return Integer.compare(nums2[a[1]], nums2[b[1]]);
});
int limit = Math.min(n, k);
for (int i = 0; i < limit; i++) heap.add(new int[] { i, 0 });
List<int[]> out = new ArrayList<>();
while (out.size() < k && !heap.isEmpty()) {
int[] cur = heap.poll();
out.add(new int[] { nums1[cur[0]], nums2[cur[1]] });
if (cur[1] + 1 < m) heap.add(new int[] { cur[0], cur[1] + 1 });
}
return out.toArray(new int[0][]);
}C++
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int n = (int) nums1.size(), m = (int) nums2.size();
auto cmp = [&](const pair<int,int>& a, const pair<int,int>& b) {
long long sa = (long long) nums1[a.first] + nums2[a.second];
long long sb = (long long) nums1[b.first] + nums2[b.second];
if (sa != sb) return sa > sb;
if (nums1[a.first] != nums1[b.first]) return nums1[a.first] > nums1[b.first];
return nums2[a.second] > nums2[b.second];
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> heap(cmp);
int limit = min(n, k);
for (int i = 0; i < limit; i++) heap.push({ i, 0 });
vector<vector<int>> out;
while ((int) out.size() < k && !heap.empty()) {
auto cur = heap.top();
heap.pop();
out.push_back({ nums1[cur.first], nums2[cur.second] });
if (cur.second + 1 < m) heap.push({ cur.first, cur.second + 1 });
}
return out;
}JavaScript
var kSmallestPairs = function(nums1, nums2, k) {
var n = nums1.length, m = nums2.length;
var heap = [];
var less = function(a, b) {
var sa = nums1[a[0]] + nums2[a[1]], sb = nums1[b[0]] + nums2[b[1]];
if (sa !== sb) return sa < sb;
if (nums1[a[0]] !== nums1[b[0]]) return nums1[a[0]] < nums1[b[0]];
return nums2[a[1]] < nums2[b[1]];
};
var push = function(v) {
heap.push(v);
var i = heap.length - 1;
while (i > 0) {
var p = (i - 1) >> 1;
if (!less(heap[i], heap[p])) break;
var t = heap[p]; heap[p] = heap[i]; heap[i] = t;
i = p;
}
};
var pop = function() {
var top = heap[0];
var last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
var i = 0;
for (;;) {
var l = 2 * i + 1, r = l + 1, s = i;
if (l < heap.length && less(heap[l], heap[s])) s = l;
if (r < heap.length && less(heap[r], heap[s])) s = r;
if (s === i) break;
var t = heap[s]; heap[s] = heap[i]; heap[i] = t;
i = s;
}
}
return top;
};
var limit = Math.min(n, k);
for (var i2 = 0; i2 < limit; i2++) push([i2, 0]);
var out = [];
while (out.length < k && heap.length > 0) {
var cur = pop();
out.push([nums1[cur[0]], nums2[cur[1]]]);
if (cur[1] + 1 < m) push([cur[0], cur[1] + 1]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Heaps and Priority Queues