#373 Find K Pairs with Smallest Sums
the problem
In plain words
You get two integer arrays nums1 and nums2, both sorted in non-decreasing order, and an integer k. A pair takes one value from nums1 and one from nums2. Return the k pairs with the smallest sums, each written as [u, v]. Any order of the pairs is accepted.
in nums1 = [1,7,11], nums2 = [2,4,6], k = 3
out [[1,2],[1,4],[1,6]]
In sum order the pairs go [1,2]=3, [1,4]=5, [1,6]=7, [7,2]=9, … — take the first three.
in nums1 = [1,1,2], nums2 = [1,2,3], k = 2
out [[1,1],[1,1]]
The two 1s in nums1 are different elements, so [1,1] appears twice.
- 1 ≤ nums1.length, nums2.length ≤ 10⁵
- -10⁹ ≤ nums1[i], nums2[i] ≤ 10⁹
- Both arrays are sorted in non-decreasing order
- 1 ≤ k ≤ 10⁴ and k ≤ nums1.length · nums2.length
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternK-way mergeTop-k with a size-k heap
Picture the table of all sums: row i is nums1[i] + nums2[0], nums1[i] + nums2[1], … — every row is already sorted. So this is merge k sorted lists, stopped after k items, on a table you never build.
solutions
From brute force to optimal
Only the first k values of each array can matter, so build those pairs, sort by sum, take k.
- A pair that uses index ≥ k has at least k pairs with smaller-or-equal sums in front of it, so skip it.
- Build all min(n₁, k) · min(n₂, k) pairs.
- Sort by sum and keep the first k.
Up to k² pairs (10⁸ when k = 10⁴) plus a sort — far too slow and too much memory at the limits.
Every candidate pair is stored.
class Solution { public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { List<int[]> pairs = new ArrayList<>(); // only the first k values of each array can ever be needed for (int i = 0; i < Math.min(nums1.length, k); i++) for (int j = 0; j < Math.min(nums2.length, k); j++) pairs.add(new int[] {nums1[i], nums2[j]}); pairs.sort(Comparator.comparingInt(p -> p[0] + p[1])); // |sum| ≤ 2·10⁹ still fits in an int List<List<Integer>> result = new ArrayList<>(); for (int t = 0; t < k && t < pairs.size(); t++) result.add(List.of(pairs.get(t)[0], pairs.get(t)[1])); return result; }}Keep one cursor (i, j) per row in a min-heap ordered by nums1[i] + nums2[j]; each poll moves that row's cursor right.
- Offer the cursor (i, 0) for every row i < min(n₁, k).
- Poll the cursor with the smallest sum and record [nums1[i], nums2[j]].
- If j + 1 < n₂, offer (i, j + 1) — the next pair in that row.
- Stop after k pairs.
k polls and at most k offers on a heap that holds at most one cursor per row (≤ min(n₁, k) rows).
The heap of row cursors (the k answer pairs aside).
class Solution { public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { // a cursor {i, j} stands for the pair (nums1[i], nums2[j]); smallest sum on top. // comparingInt, never (a, b) -> sumA - sumB: two sums can differ by 4·10⁹ and overflow PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(c -> nums1[c[0]] + nums2[c[1]])); for (int i = 0; i < Math.min(nums1.length, k); i++) heap.offer(new int[] {i, 0}); // head of every row List<List<Integer>> result = new ArrayList<>(); while (result.size() < k && !heap.isEmpty()) { int[] c = heap.poll(); // smallest sum not taken yet result.add(List.of(nums1[c[0]], nums2[c[1]])); if (c[1] + 1 < nums2.length) heap.offer(new int[] {c[0], c[1] + 1}); // next pair in the same row } return result; }}in the room
How to say it in the interview
talk track
- Draw the sum table for example 1 and point out that every row is sorted — then say "this is merge k sorted lists".
- Explain why only min(n₁, k) rows need a cursor in the heap at the start.
- Mention the comparator: compare sums with
comparingInt— never subtract two sums.
traps
- Putting every (i, j) pair in the heap — n₁·n₂ can be 10¹⁰.
- Comparator
(a, b) -> sumA - sumB: each sum fits in an int (|sum| ≤ 2·10⁹), but the difference of two sums can reach 4·10⁹ and overflow. - Starting from (0, 0) and offering both (i + 1, j) and (i, j + 1) without a visited set — the same pair gets in twice.
what they ask next
Follow-ups
Kth Smallest Element in a Sorted Matrix (LC 378)?
The same row-cursor heap, polled k times. Or binary-search the value and count entries ≤ mid with a staircase walk in O(n) per step.
Only the k-th smallest sum, not the pairs?
Binary-search on the sum; count pairs with sum ≤ mid using two pointers (one moving right in nums1, one moving left in nums2) in O(n₁ + n₂) per step.
before you submit
Edge cases to test
- k = n₁ · n₂: every pair is returned.
- Duplicates: [1,1,2] and [1,2,3], k = 2 → [[1,1],[1,1]] — equal values at different indices are different pairs.
- Sums near ±2·10⁹ still fit in an int, but their difference does not — compare, don't subtract.
- nums1 has one value: the answer pairs it with the first k values of nums2.
practise next
Similar problems
- #23Merge k Sorted ListsHardin Heaps
- #632Smallest Range Covering Elements from K ListsHardin Heaps
- #167Two Sum II - Input Array Is SortedMediumin Two Pointers