See the original problem on HackerRank.
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 sort-based solution
Suppose we sort the prices \( p \) in ascending order. Consider the sum \( p + p[n-1] \) 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 2-pointer 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 linear-time sorting algorithm since the domain is small.
Lookup-efficient 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:
- the particular condition
freq[x] > (x == p[i])is just syntactic sugar to say “if
p[i]then I need one value more in the frequency table since the first one is for
p[i], so I need at least 2. Otherwise, 1 is ok”;
- we divide searching the vector into two parts: first, from the beginning to
iexcluded and, possibly, from
i + 1to the end. This way we still use
findwithout extra logic nor custom lambdas. The idea is just to avoid finding
x == p[i].