Given a vector and a target sum, returns zero-based indices of any two distinct elements whose sum is equal to the target sum

Question

I am trying to solve 4. Two Sum from this set of C++ interview questions. As far as I can think this solution has a time complexity of \$O(n \log n)\$ can it be further optimized?

Write a function that, given a vector and a target sum, returns zero-based indices of any two distinct elements whose sum is equal to the target sum. If there are no such elements, the function should return (-1, -1).

For example, findTwoSum({ 1, 3, 5, 7, 9 }, 12) should return a std::pair<int, int> containing any of the following pairs of indices:

• 1 and 4 (3 + 9 = 12)
• 2 and 3 (5 + 7 = 12)
• 3 and 2 (7 + 5 = 12)
• 4 and 1 (9 + 3 = 12)

Here is my approach considering that negative numbers cannot be present in vector

static std::pair<int, int> findTwoSum(const std::vector<int>& list, int sum)
{
 std::vector<int> com;
 std::vector<int>::iterator it;
 for(unsigned count=0; count<list.size(); count++){
 it = std::find(com.begin(), com.end(), list[count]);
 if ( it != com.end() ){
 return std::make_pair(it - com.begin() + 1, --count);
 }
 else{
 if(sum >= list[count])
 com.push_back(sum-list[count]);
 }
 }
 return std::make_pair(-1,-1);
}

• Loki Astari: looks like O(n^2)
• Martin R: Have a look at Finding indices of numbers that sum to a target ...
• Mateusz Grzejek: Currently, it has the complexity of O(n^2). In worst case you will be traversing whole list, which gives you O(n) for the traversal itself. In addition, in each iteration you do a linear search (std::find) which gives you O(n^2) in total.
• chux: Improvement: Sort the list O(n * lg n). Marching from the left and right to find a sum is likely O(n).
• CMouse: I understand that the complexity is O(n^2), can anyone give the algorithm here ?

Answer 1

Normally, we'd use the vector's index type (std::vector<int>::size_type, i.e. std::size_t) for the return values. But unfortunately we're required to return negative values when the search fails, so I'd recommend a pair of std::ptrdiff_t instead. And the question specifically asks for ints, so I'd just insert a comment explaining that were limited to arrays of up to INT_MAX elements (the O(n2) scaling probably reduces the practical range, anyway).

---

I don't see anywhere that says there can't be negative numbers present - if that's specified, then it would have been wise to quote that part. As it is, you've introduced a bug - because we're not storing numbers larger than sum into com, the index calculation it - com.begin() + 1 will be incorrect by the amount of omitted large numbers (also, where does the +1 come from? - did you misread zero-based indices in the question?).

---

The vector com could grow to (in the worst case) the same size as the input vector. That's quite a lot of extra storage. It might be more efficient to leave the >= sum elements in place, and just search the beginning half of the input vector (no extra storage needed).

That looks like the following (making a few other simplifications, such as using an iterator instead of count, and reducing the scope of the find result):

static std::pair<int, int> findTwoSum(const std::vector<int>& list, int sum)
{
 for (auto it_b = list.begin(); it_b != list.end(); ++it_b) {
 if (auto it_a = std::find(list.begin(), it_b, sum - *it_b); it_a != it_b) {
 return {it_a - list.begin(), it_b - list.begin()};
 }
 }
 return {-1, -1};
}

---

We still have a pretty inefficient algorithm - it's O(n2), where n is the length of list, because for every element in list, we perform a linear search for its complement. We can reduce that, at the cost of reintroducing extra storage, by maintaining a set of seen values. That may seem little different to the present approach of maintaining a vector, but the advantage is that search scales much better with size. What we actually need is a map, as we'll want to note the corresponding index to return as result; the best choice is std::unordered_map:

Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.

That gives us:

 std::unordered_map<int, int> seen; // value -> index
 for (auto it_b = list.begin(); it_b != list.end(); ++it_b) {
 if (auto it_a = seen.find(sum - *it_b); it_a != seen.end()) {
 return {it_a->second, it_b - list.begin()};
 } else {
 seen[*it_b] = it_b - list.begin();
 }
 }

---

Modified code

#include <unordered_map>
#include <utility>
#include <vector>
static std::pair<int, int> findTwoSum(const std::vector<int>& list, int sum)
{
 std::unordered_map<int, int> seen; // value -> index
 for (auto it_b = list.begin(); it_b != list.end(); ++it_b) {
 if (auto it_a = seen.find(sum - *it_b); it_a != seen.end()) {
 return {it_a->second, it_b - list.begin()};
 } else {
 seen[*it_b] = it_b - list.begin();
 }
 }
 return {-1, -1};
}

And a very simple test program:

#include <iostream>
int main()
{
 auto const [a, b] = findTwoSum({ 1, 3, 5, 7, 9 }, 12);
 std::cout << a << ',' << b << '\n';
}

• L. F.: +1, although technically average \$O(1)\$ isn't necessarily \$O(1)\$.
• user673679: Is ssize_t in namespace std? (I thought adding stuff to namespace std was Not Allowed, though I guess Posix might ignore that?) Perhaps std::ptrdiff_t would be a more portable option.
• Toby Speight: @user673679, I thought ssize_t was standard, but seems I was mistaken. std::ptrdiff_t does seem to be the most suitable choice. Thanks.