Find K Pairs with Smallest Sums (Java)

Spread the love

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.

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

Example: 

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

Return: [1,2],[1,4],[1,6]

The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Java Solution

The basic idea is using an array to track the index of the next element in the other array.

The best way to understand this solution is by using an example such as nums1={1,3,11} and nums2={2,4,8}.

public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    int total=nums1.length*nums2.length;
    if(total<k){
        k=total;
    }
 
    List<int[]> result = new ArrayList<int[]>();
    int[] idx = new int[nums1.length];//track each element's cursor in nums2
    while(k>0){
        int min=Integer.MAX_VALUE;
        int minIdx=-1;
        for(int i=0; i<nums1.length; i++){
            if(idx[i]<nums2.length && nums1[i]+nums2[idx[i]]<min){
                minIdx=i;
                min=nums1[i]+nums2[idx[i]];
            }
        }
        result.add(new int[]{nums1[minIdx],nums2[idx[minIdx]]});
        idx[minIdx]++;
        k--;
    }
 
    return result;
}

Tags: ,