Happy Monday! Hope your day and week has started on the right note. With travel opening in Europe many are making plans and some are already travelling to Europe. It seems that most countries are eager and hopefully able to receive visitors in a safe manner.
Spoke with my youngest son this morning. He was heading to his office. Since the pandemic started he has been working from home like most people in the world has including me. Since the pandemic appears to be under control in many countries, including the USA, schedules are quickly changing and most people will be full time at the office at their place of work. Some companies will allow more flexibility than before with schedules allowing employees to work one or two days from home. Keep in mind that most studies have determined that face contact and casual meetings are associated with more productivity. Interesting fact, because most of us thought that chatting by the water cooler was a complete waste of time!
Today I will attempt to solve LeetCode 373. Find K Pairs with Smallest Sums. Let’s take a look at the requirements for the problem:
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. Constraints: o 1 <= nums1.length, nums2.length <= 104 o -109 <= nums1[i], nums2[i] <= 109 o nums1 and nums2 both are sorted in ascending order. o 1 <= k <= 1000
We are given two sorted in ascending order arrays of integers and an integer `k`.
With such information at hand we need to generate a set of pairs with the first element from the first array and the second from the second one. The idea is that the set of pairs must be able to produce the smallest sums.
We will be attempting a solution using the Java programming language and the VSCode IDE on a Windows machine. Unless you have a compelling reason not to use the on-line IDE provided by LeetCode, you should solve it on-line. That way you will not have to generate test code to collect the input data, call the function of interest and display results.
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
}
The signature for the function of interest follows the requirements. We are provided two int[] arrays with sorted in ascending order values and an integer value that specifies the number of pairs we need to generate.
3 1,7,11 2,4,6 main <<< k: 3 main <<< nums1: [1, 7, 11] main <<< nums2: [2, 4, 6] main <<< pairs: [[1, 6], [1, 2], [1, 4]] 2 1,1,2 1,2,3 main <<< k: 2 main <<< nums1: [1, 1, 2] main <<< nums2: [1, 2, 3] main <<< pairs: [[1, 1], [1, 1]] 3 1,2 3 main <<< k: 3 main <<< nums1: [1, 2] main <<< nums2: [3] main <<< pairs: [[2, 3], [1, 3]] 5 1,2 1,3 main <<< k: 5 main <<< nums1: [1, 2] main <<< nums2: [1, 3] main <<< pairs: [[2, 3], [1, 3], [2, 1], [1, 1]] 3 1 2,4,5,9 main <<< k: 3 main <<< nums1: [1] main <<< nums2: [2, 4, 5, 9] main <<< pairs: [[1, 5], [1, 2], [1, 4]]
Our test code reads the first three input lines. The first line contains the value for `k`. The next line holds the values for the `nums1` array and the third line the vales for the `nums2` array of integers.
Our test code seems to display the input values. I like to do so to make sure all is well before passing the values as arguments to the function of interest.
It seems that our test scaffold calls the function of interest and then displays the results.
I was not sure if we had to return the pairs in any specified order. Initially I returned them in ascending order. As you can see in the requirements, there is no specific order for the pairs, just their values. When solving problems, make sure you capture all the information and interpret it in such a way not to perform additional tasks that take time to develop and execute.
/**
* Test scaffold.
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read k ****
int k = Integer.parseInt(br.readLine().trim());
// **** read nums1 array ****
int[] nums1 = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** read nums2 array ****
int[] nums2 = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< k: " + k);
System.out.println("main <<< nums1: " + Arrays.toString(nums1));
System.out.println("main <<< nums2: " + Arrays.toString(nums2));
// **** call function of interest and display result ****
System.out.println("main <<< pairs: " + kSmallestPairs(nums1, nums2, k));
}
The test code seems to closely do what we discussed for the test cases. Not much to add at this time.
/**
* 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.
*
* Runtime: 14 ms, faster than 40.74% of Java online submissions.
* Memory Usage: 39.6 MB, less than 80.78% of Java online submissions.
*/
static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
// **** create priority queue with comparator ****
PriorityQueue<List<Integer>> pq = new PriorityQueue<>(
k,
(a, b) -> ((b.get(0) + b.get(1)) - (a.get(0) + a.get(1)))
);
// **** populate priority queue O(n * m) ****
int maxVal = Integer.MIN_VALUE;
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
// **** add pair to priority queue *****
if (pq.size() < k) {
// **** add pair to the priority queue ****
pq.add(Arrays.asList(nums1[i], nums2[j]));
// **** update max value (if needed) ****
if (nums1[i] + nums2[j] > maxVal)
maxVal = nums1[i] + nums2[j];
} else {
// **** pair smaller than max value in priority queue ****
if (nums1[i] + nums2[j] < maxVal) {
// **** remove head (largest value in pq) ****
pq.remove();
// **** add current pair ****
pq.add(Arrays.asList(nums1[i], nums2[j]));
// **** get pair at head of the priority queue (largest value in pq) ****
List<Integer> pair = pq.peek();
// **** update max value ****
maxVal = pair.get(0) + pair.get(1);
}
}
}
}
// **** return list of pairs ****
return new ArrayList<>(pq);
}
It made sense to me to use a priority queue. That way our values will be ordered in ascending or descending order. Using such approach, our answer would be found in the ending or beginning pairs in the priority queue. This is dependent on the comparator that we implement.
I decided to implement a comparator as a separate class which contained the two array values and the sum. After a few passes I removed the comparator class and went with a lambda expression.
We start by creating a priority queue with a specific size and comparator. Our comparator takes two pairs and computes the difference of the sums of the associated pairs. The current comparator generates a priority queue with descending values. That way we will hold no more than `k` entries in the priority queue which should match the `k` pairs we need to return as a solution.
We then enter a loop in which we generate all combinations of pairs using one value from `nums1` and the other from `nums2`.
Note that we declare a `maxVal` integer variable that we use to help us maintain the smallest value pairs in the priority queue.
Of each pair we check if the size of the priority queue is smaller than `k`. If so, we add the current pair to the priority queue updating the max value if needed.
If we determine we have `k` elements in the priority queue, then we only want to add pairs to the priority queue whose sum is less than the `maxVal`. Note that we want to hold in the priority queue pairs that meet the requirements for the answer.
If the current pair meets expectations, we remove the pair at the head of the queue which is associated with the `maxVal`. We remove it from the priority queue, add the current pair, get the value of the pair at the head of the priority queue and update the `maxVal` variable.
After we are done with the loop, our priority queue should hold `k` or less elements. We generate an array list with the pairs in the priority queue and return them as our answer.
The execution time and memory usage is in the comments section of the function of interest.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John