Find K Pairs with Smallest Sums

Question

The question is this:

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

My first idea was to find all the sums, and then add it to a minheap, but the time complexity for that is very large I think O(n^2logn).

I can't understand how to optimize the solution to make it faster.

Here is my code for going through all iterations of possible sums then adding them to a min heap. I was wondering how to optimize this code to make it run in O(nlogn).

public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
     HashMap<ArrayList<Integer>, Integer> all_values = new HashMap<ArrayList<Integer>, Integer>();
     PriorityQueue<Map.Entry<ArrayList<Integer>, Integer>> k_pairs = new PriorityQueue<Map.Entry<ArrayList<Integer>, Integer>>(
     (a,b) -> b.getValue().compareTo(a.getValue())
     );
     for(int i = 0; i < nums1.length; i++){
        for(int j = 0; j <  nums2.length; j++){
            ArrayList<Integer> temp = new ArrayList<Integer>();
            temp.add(i);
            temp.add(j);
            all_values.put(temp, nums1[i] + nums2[j]);

        }
     }
        
    for(Map.Entry<ArrayList<Integer>, Integer> o : all_values.entrySet()){
        k_pairs.offer(o);
        if(k_pairs.size() > k){
            k_pairs.poll();
        }
    }
        
    List<List<Integer>> final_all_k = new ArrayList<List<Integer>>();
    while(k_pairs.size() > 0){
        List<Integer> temp = k_pairs.poll().getKey();
        int temp_index1 = nums1[temp.get(0)];
        int temp_index2 = nums2[temp.get(1)];
        temp.clear();
        temp.add(temp_index1);
        temp.add(temp_index2);
        final_all_k.add(temp);
        
    }
    
     return final_all_k;
}

Answer 1

Assuming the following is in fact your objective (that I'm not misinterpreting your question):

Minimize: max(u1 + v1, u2 + v2, ..., uk + vk)

You can simply take the first k elements of each list (which will be the smallest k of each), reverse one of the sublists, and pair them.

---

Proof

We can ignore the latter n-k elements because if any of those elements were used in the "smallest" pairs, we'd just swap that value out for an unused element in the first k elements, for a smaller valued pair.

We can group them up by reversing one sublist and pairing because this is optimal. To make this obvious, consider some variables a, b, c, and d. Lets say we pair them up like: (b, d), (a, c), we could also write this out:

list1: ..., b, a, ...
list2: ..., d, c, ...

Now, suppose that I tell you that c < d and a < b. Since list2 is reversed, c < d would put d before c, just like we have it- good. But a < b would imply that a should precede b, which it does not. For any such inversion, we can safely invert the two elements for a smaller sum.

list1: ..., a, b, ...
list2: ..., d, c, ...

This results in the pairs (a, d) and (b, c), so R2 = max(..., a+d, b+c, ...) instead of R1 = max(..., b+d, a+c, ...). Now, we said that a < b and c < d, so a+c < b+d, so R1 = max(..., b+d, ...). We can also simplify R2, by substituting a with b (since a < b) and c with d (since c < d), giving

R2 = max(..., a+d, b+c, ...) < max(..., b+d, b+d, ...) = max(..., b+d, ...) = R1

So R2 < R1, our inversion reduced the max sum.

Repeating this until there's no inversions left, we're left with two sorted sublists- one in ascending order, and one descending.