Find K Pairs with Smallest Sums

MediumK-way Merge · Min-Heap🧩 K-Way Merge LeetCode #373 ↗Updated Oct 30, 2026

Problem

You get two arrays nums1 and nums2, each sorted in non-decreasing order, and an integer k. A pair takes one element from each array. Return the k pairs [u, v] whose sums u + v are the smallest (any order; when sums tie, any valid choice is accepted).

Inputnums1 = [1,7,11], nums2 = [2,4,6], k = 3Output[[1,2],[1,4],[1,6]]

Inputnums1 = [1,1,2], nums2 = [1,2,3], k = 2Output[[1,1],[1,1]]

1 ≤ m, n ≤ 10⁵ · -10⁹ ≤ values ≤ 10⁹ · 1 ≤ k ≤ min(10⁴, m·n)

Try it yourself

Java

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

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Picture an m×n grid of sums: every row i is sorted (nums1[i] + nums2[0..]). Taking the k smallest is a k-way merge of sorted rows — keep each row's next candidate in a min-heap and pop k times.

PatternK-Way Merge

Instinct Several sorted lists, rows or streams and you need the global order, the k-th smallest or a range: keep one cursor per list in a min-heap.

Memory hack Line up the heads, crown the smallest, then let its next-in-line step up.

Open the K-Way Merge guide →

Approaches

Brute ForceGenerate All Pairs, Sort by Sum

Time O(mn log(mn))Space O(mn)

Materialise every (i, j) pair, sort by nums1[i] + nums2[j] and keep the first k. Ignores the fact that both inputs are already sorted.

Java

public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    List<int[]> all = new ArrayList<>();
    for (int a : nums1) {
        for (int b : nums2) all.add(new int[]{a, b});
    }
    // Integer.compare avoids overflow of (sumA - sumB)
    all.sort((p, q) -> Integer.compare(p[0] + p[1], q[0] + q[1]));
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < k; i++) res.add(List.of(all.get(i)[0], all.get(i)[1]));
    return res;
}

Up to 10¹⁰ pairs at the limits — only a reference answer.

BetterBounded Max-Heap with Early Breaks

Time O(min(m,k) · min(n,k) · log k)Space O(k)

Keep the best k pairs seen so far in a max-heap keyed by sum. Scan rows in order; once the heap is full and the current sum is not below its top, the rest of this row (sorted nums2) can't help, so break. If even j = 0 fails, later rows can't help either.

Java

public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    // max-heap on sum: the root is the worst of the current best-k
    PriorityQueue<int[]> heap = new PriorityQueue<>(
        (p, q) -> Integer.compare(q[0] + q[1], p[0] + p[1]));
    for (int i = 0; i < Math.min(nums1.length, k); i++) {
        boolean usedRow = false;
        for (int j = 0; j < Math.min(nums2.length, k); j++) {
            int sum = nums1[i] + nums2[j];
            if (heap.size() == k) {
                int[] top = heap.peek();
                if (sum >= top[0] + top[1]) break; // rest of the row is larger
                heap.poll();
            }
            heap.add(new int[]{nums1[i], nums2[j]});
            usedRow = true;
        }
        if (!usedRow) break; // even nums2[0] was too big, later rows are bigger
    }
    List<List<Integer>> res = new ArrayList<>();
    for (int[] p : heap) res.add(List.of(p[0], p[1]));
    return res;
}

Uses sortedness to prune, but can still touch ~k² pairs.

OptimalK-way Merge with a Min-Heap of Row Heads

Time O(k log min(m, k))Space O(min(m, k))

Seed the heap with (i, 0) for the first min(m, k) rows. Each pop is the next smallest sum overall; after popping (i, j) push its row successor (i, j+1). Every row is sorted and every unseen cell is ≥ its row's head, so k pops yield the k smallest.

Java

public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    // heap entries: {i, j}, ordered by nums1[i] + nums2[j]
    PriorityQueue<int[]> heap = new PriorityQueue<>((p, q) -> Integer.compare(
        nums1[p[0]] + nums2[p[1]], nums1[q[0]] + nums2[q[1]]));
    for (int i = 0; i < Math.min(nums1.length, k); i++) heap.add(new int[]{i, 0});
    List<List<Integer>> res = new ArrayList<>();
    while (res.size() < k && !heap.isEmpty()) {
        int[] cur = heap.poll();
        int i = cur[0], j = cur[1];
        res.add(List.of(nums1[i], nums2[j]));
        if (j + 1 < nums2.length) heap.add(new int[]{i, j + 1});
    }
    return res;
}

Touches only k + min(m, k) cells; the heap never exceeds min(m, k).

Pro tip

Rows beyond index k-1 never matter: the k cells (0..k-1, 0) already have sums no larger than any cell in them.

At a glance

Level	Approach	Time	Space
Brute Force	Generate All Pairs, Sort by Sum	`O(mn log(mn))`	`O(mn)`
Better	Bounded Max-Heap with Early Breaks	`O(min(m,k) · min(n,k) · log k)`	`O(k)`
Optimal	K-way Merge with a Min-Heap of Row Heads	`O(k log min(m, k))`	`O(min(m, k))`

Common pitfalls

Comparator (a, b) -> sumA - sumB overflows when sums span ±2·10⁹.
Seeding both (i+1, j) and (i, j+1) without a visited set pushes duplicates.
Seeding all m rows: harmless for correctness but O(m) work when k is much smaller.

Interview tips

Draw the sum grid; sorted rows make the merge analogy obvious.
Mention it's the same skeleton as Merge k Sorted Lists (23) and Kth Smallest in a Sorted Matrix (378).
Clarify that ties may be returned in any order — tests should compare sums, not exact pairs.

Pattern

K-way merge → k smallest items across several sorted sequences (rows of a sorted grid).

My notes saved in this browser