Command Palette

Search for a command to run...

Hectal
Problem 42.8 · Pattern Recognition DrillsMedium

Find K Pairs with Smallest Sums

What it teaches:

Practise it on judges as “Find K Pairs with Smallest Sums”.

In plain words

Picture a table: row i is nums1[i], column j is nums2[j], and each cell holds their sum. Because both lists are sorted, sums grow to the right in each row. So the smallest unused sum is always the leftmost unused cell of some row. Keep just those front cells in a pile that hands you the smallest one; each time you take a cell, add the next cell of the same row.

Return the k pairs with the smallest sums. Example: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 → [[1,2],[1,4],[1,6]].

The problem

Given two sorted arrays, return the k pairs (u, v), u from nums1 and v from nums2, with the smallest sums (any order among equal sums).

Example 1

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]

Constraints

  • 1 ≤ lengths ≤ 10⁵
  • 1 ≤ k ≤ 10⁴

Pattern clues in the wording

  • → Sorted inputs
  • → k smallest combinations

Stuck? Take one hint at a time

Solution · starter
import java.util.*;

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
nums1 = [1,7,11]
nums2 = [2,4,6]
k = 3
[[1,2],[1,4],[1,6]]
2
nums1 = [1,1,2]
nums2 = [1,2,3]
k = 2
[[1,1],[1,1]]

From slow to fast

Approaches

1. Heap over row heads · O(k log k)
1

Heap over row heads

Time O(k log k) Space O(k)

Heap of (sum, i, j). Pop k times; after popping (i, j), push (i, j + 1).

▶ Dry run: One front cell per row in a min-heapnums1 = [1,7,11], nums2 = [2,4,6], k = 3
3
5
7
9
11
13
13
15
17

min-heap(list)

3 (1+2)9 (7+2)13 (11+2)

out(list)

empty

Step 1/4Rows are nums1, columns nums2, cells are sums. Put the first cell of each row in the heap.

Approach 1
import java.util.*;

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 0; i < Math.min(nums1.length, k); i++) pq.offer(new int[]{nums1[i] + nums2[0], i, 0});
        List<List<Integer>> out = new ArrayList<>();
        while (!pq.isEmpty() && out.size() < k) {
            int[] t = pq.poll();
            out.add(List.of(nums1[t[1]], nums2[t[2]]));
            if (t[2] + 1 < nums2.length) pq.offer(new int[]{nums1[t[1]] + nums2[t[2] + 1], t[1], t[2] + 1});
        }
        return out;
    }
}

Verdict: Never builds all n × m pairs.

Before you submit

Edge cases and common mistakes

Test these inputs

  • k larger than all pairs
  • Duplicate values

Mistakes people make

  • Generating all pairs and sorting (n × m can be 10¹⁰).

Interview

Follow-up questions

Which course problem has the same shape?