See the original problem on HackerRank.
Solutions
The brute force approach is easy: just run two nested loops and for each value \( x \) find if it exists a value equals to \( target  x \). This solution is quadratic.
Efficient solutions are based either on sorting or additional storage (e.g. frequency table, hash maps).
A sortbased solution
Suppose we sort the prices \( p \) in ascending order. Consider the sum \( p[0] + p[n1] \) where \( n \) is the number of available prices. If this sum was less than \( m \), then we should increment the left hand index (we need to “pay more”). On the other hand, if the sum was greater than \( m \), then we should decrement the right hand index (we need to “pay less”). This leads to the following solution based on 2pointer technique:


Clearly, some additional storage is needed to sort the array without losing the original indexes.
The overall complexity is \( O(N \cdot logN \) but it can be even optimized by using a lineartime sorting algorithm since the domain is small.
Lookupefficient data structures solutions
Another approach consists in using a multimap (since duplicates are possible) to lookup every value efficiently:


A variation of this approach consists in using a frequency table. In this case, we do not keep track of the indexes with a sort of trick: when we find the matching price (\( m  p[i] \)), we just scan the array to find its position. Since this operation is perfomed only once, the solution stays linear:


Two notes:
 the particular condition
freq[x] > (x == p[i])
is just syntactic sugar to say “ifx
isp[i]
then I need one value more in the frequency table since the first one is forp[i]
, so I need at least 2. Otherwise, 1 is ok”;  we divide searching the vector into two parts: first, from the beginning to
i
excluded and, possibly, fromi + 1
to the end. This way we still usefind
without extra logic nor custom lambdas. The idea is just to avoid findingp[i]
whenx == p[i]
.