Find K Pairs with Smallest Sum (Leetcode 373/Lintcode 1274)[Solution Illustrated]
--
Problem — Find K Pairs with Smallest Sums
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.
Return results need to be orderly.
Example:
Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Return: [1,2],[1,4],[1,6]
First Step
The two arrays are monotonic increasing. So it stands to reason that the first elements in each of the arrays when summed, will give the pair with smallest sum. From the diagram below, the indices of the smallest pair would be [idx1=0, idx2=0]. The smallest sum is thus 1 + 2 = 3.
Insight — How to get second smallest pair?
Let’s take a while to represent each pairs in terms of a triplet tuple consisting of the sum (of elements — one from num1 and one from num2), the index of array num1 and the index element of array num2.
Once this representation is defined and out of the way, let’s tackle how to get the next smallest pair.
Since we know the current smallest pair, the sum for the next pair could be based on one index adjacent to the right of the current idx1 of array1 or one index adjacent to the right of the current idx2 of array1, while keeping the other index in the pair the same. This is since the elements to the right of the current one is always higher in the two arrays. Visually this is shown as:
How to decide the next smallest pair?
So every time we find the current smallest pair, we can derive up to two possible candidates for the next pair. How to decide? Answer: We use what we learnt a min heap or smallest priority queue. In the diagram below, the correct next smallest pair of [0, 1] is found.
So what happen to the tuple (7+2, 1, 0)? It’s important to note that it stays within the min heap ready to be “popped” out if it has the smallest sum. At this point, it’s important to note that only one unique tuple should ever be added to the min heap during the “push”. To do this, one could employ a set to check whether a tuple had ever been added to the min heap before.
Two Edge Cases To Handle
(1) In the pairing, you could reach the case where there are simple no each pairs to reach k pairs. In this case, just return all the possible pairs.
(2) Again in the pairing, you could reach the end of one array, in this case, form potential tuples by holding that end constant.
Finale, show me the Code
Performance in Leetcode
Runtime: 48 ms, faster than 85.18% of Python3 online submissions for Find K Pairs with Smallest Sums.Memory Usage: 14.8 MB, less than 47.68% of Python3 online submissions for Find K Pairs with Smallest Sums.
Happy coding! Feel free to optimise further. Share if you do.
