← Back to Index

📚 Find K Pairs with Smallest Sums – Java Cheat Sheet

📌 What Is It?

The problem involves finding the K pairs with the smallest sums from two sorted arrays. Each pair consists of one element from each array.

This problem can be efficiently solved using a min-heap to track the smallest sums and their corresponding pairs.

🧱 Pattern Template

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> (nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]]));
        List<List<Integer>> result = new ArrayList<>();

        // Step 1: Add the first pair from each element in nums1 with the first element in nums2
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            minHeap.offer(new int[]{i, 0}); // [index in nums1, index in nums2]
        }

        // Step 2: Extract the smallest pairs from the heap
        while (!minHeap.isEmpty() && k > 0) {
            int[] smallest = minHeap.poll();
            int i = smallest[0];
            int j = smallest[1];
            result.add(List.of(nums1[i], nums2[j]));

            // Add the next pair from nums2 for the same element in nums1
            if (j + 1 < nums2.length) {
                minHeap.offer(new int[]{i, j + 1});
            }

            k--;
        }

        return result;
    }
}

📊 Time Complexity

• Heap Initialization: O(min(n, k) log k) – Adding the first k pairs to the heap.
• Heap Operations: O(k log k) – Extracting and adding elements to the heap for k pairs.
• Overall Complexity: O(k log k).

✅ Use Cases

• Finding the smallest or largest sums in two sorted arrays
• Efficiently combining sorted data streams
• Applications in optimization and scheduling problems

📘 Common LeetCode Problems

• 373. Find K Pairs with Smallest Sums [Medium] Heap

🧪 Example: Find K Pairs with Smallest Sums

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

Explanation:
- The pairs with the smallest sums are:
  1. (1,2) with sum 3
  2. (1,4) with sum 5
  3. (1,6) with sum 7

▶️ View Animation

💡 Pro Tips

• Use a min-heap to efficiently track the smallest sums and their corresponding pairs.
• Edge cases: empty arrays, k greater than the total number of pairs.
• Ensure the heap stores enough information to track the indices of the elements in both arrays.