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

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);
}

• looks like O(n^2) – Martin York Jan 30 '18 at 18:51
• Have a look at Finding indices of numbers that sum to a target ... – Martin R Jan 30 '18 at 19:00
• 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. – Mateusz Grzejek Jan 30 '18 at 19:02
• Improvement: Sort the list O(n * lg n). Marching from the left and right to find a sum is likely O(n). – chux Jan 31 '18 at 0:39
• I understand that the complexity is O(n^2), can anyone give the algorithm here ? – CMouse Feb 6 '18 at 10:15

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(n²) 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(n²), 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';
}

• +1, although technically average $O(1)$ isn't necessarily $O(1)$. – L. F. Jun 16 at 0:45
• 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. – user673679 Jun 17 at 9:23
• @user673679, I thought ssize_t was standard, but seems I was mistaken. std::ptrdiff_t does seem to be the most suitable choice. Thanks. – Toby Speight Jun 17 at 9:28