Find kth smallest pair sum with heaps

You are given two nondecreasing arrays A (length n) and B (length m) of non-negative integers and an integer k (1 <= k <= nm). Return the k-th smallest value among all pair sums A[i] + B[j]. Avoid generating all pairs. Target complexity: O(k log min(n, m)) time and O(min(n, m)) space using a heap-based approach. Discuss handling duplicate sums, boundary cases (k=1, k=nm), and prove correctness.

Find kth smallest pair sum with heaps

You are given two nondecreasing arrays A (length n) and B (length m) of non-negative integers and an integer k (1 <= k <= nm). Return the k-th smallest value among all pair sums A[i] + B[j]. You must avoid materializing all nm pairs.

Target complexity: O(k log min(n, m)) time and O(min(n, m)) extra space using a min-heap.

Approach: iterate over the shorter array so the heap holds at most min(n, m) entries. Seed the heap with the pair (smaller[i] + larger[0], i, 0) for every index i of the shorter array. Because both arrays are sorted, the smallest unseen sum is always the heap top. Pop k times; each time you pop (sum, i, j), push the next candidate in the same row (smaller[i] + larger[j+1]) if it exists. The k-th popped value is the answer. Duplicate sums are returned with multiplicity — the k-th smallest counts repeated sums separately, exactly as a fully sorted list of all pair sums would.

Return an integer (the k-th smallest pair sum).

Constraints

• 1 <= n, m
• 1 <= k <= n * m
• A and B are sorted in nondecreasing order
• All elements of A and B are non-negative integers
• Do not generate all n*m pair sums explicitly

Examples

Example 1

Input: ([1, 7, 11], [2, 4, 6], 3)
Output: 7

Explanation: All pair sums sorted: [3, 5, 7, 9, 11, 13, 13, 15, 17]. The 3rd smallest is 7 (= 1 + 6).

Example 2

Input: ([1, 1, 2], [1, 2, 3], 1)
Output: 2

Explanation: k=1 boundary: the smallest sum is A[0] + B[0] = 1 + 1 = 2.

Hints

1. The smallest pair sum is always A[0] + B[0]. The next smallest is one step right in either array — this 'frontier' is exactly what a min-heap tracks efficiently.
2. Seed the heap with one entry per row of the SHORTER array: (smaller[i] + larger[0], i, 0). This caps the heap at O(min(n, m)) entries.
3. When you pop (sum, i, j), the only new candidate it unlocks is (smaller[i] + larger[j+1], i, j+1). Push it if j+1 is in bounds. Never push a 'down' move, or you would enqueue the same cell twice.
4. Duplicate sums count with multiplicity: popping k times naturally handles ties because each (i, j) cell is a distinct heap entry even when sums are equal.