230. Find K Pairs with Smallest Sums

Because both arrays are sorted, the smallest sums form a frontier. Seed a min-heap with pairs (nums1[i], nums2[0]) for the first k rows. Each time you pop the smallest pair, push the next pair in that same row — this always exposes the next-smallest candidate.

Idea

Both arrays are sorted, so the pair with the overall smallest sum is (nums1[0], nums2[0]). From any pair (i, j), the natural next candidates are (i+1, j) and (i, j+1). To avoid duplicates and stay efficient, seed the heap with the first column (i, 0) for each row, and whenever we pop (i, j) we only push (i, j+1) — so each row advances along its columns exactly as needed.

Algorithm

1. If either array is empty, return [].
2. Push (nums1[i] + nums2[0], i, 0) for i in 0 .. min(k, len(nums1)) - 1.
3. Repeat k times (while the heap is non-empty): pop the smallest (sum, i, j), record [nums1[i], nums2[j]], and if j+1 is valid push (nums1[i] + nums2[j+1], i, j+1).

Worked example: nums1 = [1,7,11], nums2 = [2,4,6], k = 3

Pops: (1,2) sum 3 → push (1,4); (1,4) sum 5 → push (1,6); (1,6) sum 7.

Result: [[1,2],[1,4],[1,6]].

Complexity

• Time: O(k log k).
• Space: O(k) for the heap.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums1.length == 0 || nums2.length == 0) {
            return result;
        }
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) ->
            a[0] != b[0] ? Integer.compare(a[0], b[0])
                         : (a[1] != b[1] ? Integer.compare(a[1], b[1]) : Integer.compare(a[2], b[2])));
        for (int i = 0; i < Math.min(k, nums1.length); i++) {
            heap.offer(new int[]{nums1[i] + nums2[0], i, 0});
        }
        while (!heap.isEmpty() && result.size() < k) {
            int[] top = heap.poll();
            int i = top[1], j = top[2];
            result.add(Arrays.asList(nums1[i], nums2[j]));
            if (j + 1 < nums2.length) {
                heap.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
            }
        }
        return result;
    }
}