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.

Tuple Representation

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

Python 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.

--

--

--

Writing to soothe the soul, programming to achieve flow

Love podcasts or audiobooks? Learn on the go with our new app.

A struct in the C programming language (and many derivatives) is a composite data type (or record)…

Key Takeaways From Our Cloud Infrastructure Lab

Deprecating packages on nuget.org

4 Focus Areas for the Best ColdFusion Server Optimization

Crack your CKAD exam

My experience of migrating from Java projects to Golang projects

journal

StackOverFlowError: Causes & Solutions

Introducing the HandyMiner-Goldshell-GUI

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Mipsmonsta

Mipsmonsta

Writing to soothe the soul, programming to achieve flow

More from Medium

Codility Algorithm Practice Lesson 14: Binary Search Algorithm, Task 2: Nailing Planks— a Python…

Motherboard, Reverse Detail

Exploring Functional Programming

Optimisation, part 4

Organise to perform

Implementing a Heap in Python