Problem #373: Find K Pairs with Smallest Sums

Intuition & Strategy Breakdown

Use a min-heap storing tuples (nums1[i] + nums2[j], i, j). Extract smallest sum pair and push next pair (i, j+1) into heap.

Python Solution

import heapq

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        res = []
        if not nums1 or not nums2 or k <= 0:
            return res
        
        min_heap = []
        for i in range(min(len(nums1), k)):
            heapq.heappush(min_heap, (nums1[i] + nums2[0], i, 0))
        
        while k > 0 and min_heap:
            val, i, j = heapq.heappop(min_heap)
            res.append([nums1[i], nums2[j]])
            if j + 1 < len(nums2):
                heapq.heappush(min_heap, (nums1[i] + nums2[j+1], i, j+1))
            k -= 1
        return res

Java Solution

import java.util.*;

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