K pairs with smallest sums

373.Find K Pairs with Smallest Sums

Array

Heap

Design

Problem Statement:

Given two sorted arrays nums1 and nums2 of size m and n respectively and an integer k, return the k pairs (u,v) where u is from nums1 and v is from nums2 with the smallest sums.

Example:

Input:

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

→

Output:

[[1,2],[1,4],[1,6]]

Algorithm:

1. Create min heap based on sum of pairs
2. Initialize with first element of nums1
3. Poll k times while adding next nums1 element
4. Track indices to form valid pairs

Complexity:

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

Java Solution:

public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    Queue pq = new PriorityQueue<>((a, b) -> a.num1 + a.num2 - b.num1 - b.num2);
    List<int[]> res = new ArrayList<>();
    if (nums1.length == 0 || nums2.length == 0) return res;

    // Initialize with first element of nums1
    for (int i = 0; i < nums2.length; i++) {
        pq.add(new Element(0, nums1[0], nums2[i]));
    }
            
    while (k > 0) {
        Element curr = pq.poll();
        if (curr == null) break;
        res.add(new int[] {curr.num1, curr.num2});
        k--;
        if (curr.idx < nums1.length - 1)  
            pq.add(new Element(curr.idx + 1, nums1[curr.idx + 1], curr.num2));  
    }
    
    return res;  
}

class Element {
    int idx;
    int num1;
    int num2;
    
    public Element(int idx, int num1, int num2) {
        this.num1 = num1;
        this.num2 = num2;
        this.idx = idx;
    }
}

Python Solution:

def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
    if not nums1 or not nums2:
        return []
    
    heap = []
    result = []
    
    # Add first element pairs to heap
    for j in range(len(nums2)):
        heapq.heappush(heap, (nums1[0] + nums2[j], 0, nums1[0], nums2[j]))
    
    while heap and k > 0:
        _, i, num1, num2 = heapq.heappop(heap)
        result.append([num1, num2])
        k -= 1
        
        if i < len(nums1) - 1:
            heapq.heappush(heap, (nums1[i+1] + num2, i+1, nums1[i+1], num2))
    
    return result

C++ Solution:

class Solution {
public:
    struct Element {
        int idx, num1, num2;
        Element(int i, int n1, int n2) : idx(i), num1(n1), num2(n2) {}
    };
    
    vectorint>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vectorint>> result;
        if(nums1.empty() || nums2.empty()) return result;
        
        auto comp = [](const Element& a, const Element& b) {
            return a.num1 + a.num2 > b.num1 + b.num2;
        };
        priority_queue, decltype(comp)> pq(comp);
        
        // Initialize heap with first element pairs
        for(int j = 0; j < nums2.size(); j++) {
            pq.push(Element(0, nums1[0], nums2[j]));
        }
        
        while(!pq.empty() && k--) {
            Element curr = pq.top();
            pq.pop();
            result.push_back({curr.num1, curr.num2});
            
            if(curr.idx < nums1.size() - 1) {
                pq.push(Element(curr.idx + 1, nums1[curr.idx + 1], curr.num2));
            }
        }
        
        return result;
    }
};