Finding indices of numbers that sum to a target

Question

I've taken this algorithm question, which is to find the indexes of any two numbers in an array that sum to a given number. It is quite a simple problem to solve. But it is the execution time of my code algorithm that bugs me.

#include <iostream>
#include <vector>
using namespace std;

class TwoSum
{
public:
  static std::pair<int, int> findTwoSum(const std::vector<int>& list, int TargetSum)
  {
    for (int increment = 0; increment < list.size(); increment++)
    {
        for (int i = 0; i < list.size(); i++)
        {
            if (list.at(increment) + list.at(i) == TargetSum)
            {
                return make_pair(increment, i);
            }
        }
    }
    return make_pair(-1, -1);
  }
};

int main(int argc, const char* argv[])
{
   vector<int> list = {1, 3, 5, 7, 9 };
   int targetSum = 12;
   pair<int, int> indices = TwoSum::findTwoSum(list, targetSum);

   indices.first == -1 && indices.second == -1 ?
   cout << "No vector elements can be added to achieve the target sum" << endl :
   cout << "The target sum can be achieved by adding the vector element " << indices.first << " and " << indices.second;
   cout << endl;

   return 0;
}

It is guaranteed correct as I tested it with the website's compiler (or whatever you call it), they can test your code just by pasting and running it on their code editor. I tested this on my IDE as well, and it worked fine.

The problem is, my code failed the performance test when dealing with large number of vector elements as it took longer than the website's expectation. For me, the function named findTwoSum()is already straightforward. And I don't have any idea how to optimize this function. Note that the test's focus here is the function itself and how fast it executes.

Any modifications in function's return type and parameter is not allowed. As the website stated that you cannot modify the main function's contents, implying that you cannot also change how the function is called.

But I slightly modified the main function for you to know what the program is trying to achieve.

Answer 1

Not quite right

First off, you're checking every cross pair of indices against each other. But that means that findTwoSum({1, 3, 4}, 6) will succeed, even though there is no pair of elements that sum to 6 - because you count the 3 twice. You need: "any two distinct elements".

Iterating over vectors

list is a confusing name for a vector. increment is a poor variable name for this - since it's not incrementing anything, it's just another index, so you really should use i and j instead. Also you don't need at() - that member function does range checking. But your indices will all definitely be in range, so you could simply write:

for (size_t i = 0; i < v.size(); ++i) {
    for (size_t j = i+1; j < v.size(); ++j) { // correcting initial bug
        if (v[i] + v[j] == target) {
            return std::make_pair(i, j);
        }
    }
}
return std::make_pair(-1, -1);

Failure case

Rather than using sentinel values, I prefer to use something like Boost.Optional to indicate failure, so that:

boost::optional<std::pair<int, int>> findTwoSum(const std::vector<int>&, int target);

Classes

Why is findTwoSum a static member function? Just make it a free function. There's no reason for a class. You could instead make TwoSum a namespace but I don't see the point of that either.

The Algorithm

You are checking every pair of indices - that's \$O(n^2)\$. We can do way better. Consider that once we have our first index - there is one unique element that we need to find to see if we have a success case: target - v[i].

We could simply throw all of our indices into a map:

std::unordered_map<int, size_t> indices;
for (size_t i = 0; i < v.size(); ++i) {
    indices.insert(std::make_pair(v[i], i));
}

And then simply search if target - v[i] is in indices for each such i:

for (size_t i = 0; i < v.size(); ++i) {
    auto j = indices.find(target - v[i]);
    if (j != indices.end()) {
        return std::make_pair(i, j->second);
    }
}

This will be \$O(n)\$ to create the hashtable, and then another \$O(n)\$ to do all the searching... for a grand total of \$O(n)\$.

Answer 2

I see some things that may help your improve your program.

Think about a better algorithm

At the moment, for each item in the list, the code looks for a matching number in the entire list. This is \${\bf O}(n^2)\$ complexity. First, the inner loop could at least start with the next element instead of starting from 0. That would save a little time and is valid because a matching number couldn't possibly be before the outer loop's index or it would already have been found. Second, consider how one might be able to solve the problem using a single pass through the data. You would need another local data structure for this approach, but it may still be better for long arrays. Finally, you might consider using two algorithms -- one for a short list and one for a long one.

Don't abuse using namespace std

Especially in a very simple program like this, there's little reason to use that line. Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Don't abuse the trinary operator

The code currently uses the :? operator to decide which string to display. Better would be to make that into a conventional if..else construct for better clarity.

Be wary of signed versus unsigned

On some machines and for some compilers (such as gcc and clang on a Linux machine), list.size() will return an unsigned number, but it's being compared to an int within each for loop. One way to deal with that would be this:

for (decltype(list.size()) i = 0; i < list.size(); i++)

A neater way to do that would be to make a specific variable type:

using size_type = decltype(list.size());

Omit unused variables

Because argc and argv are unused, you could use the alternative form of main:

int main ()

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main. Here are some observations that may help you improve your program.

Answer 3

This piece of code returns the indices of array whose values add up to a target "sum". It handles unsorted array with duplicate entries.

In Perl with 0(n) time complexity using hash map:

#!/usr/bin/perl

use strict;

use warnings;

use Data::Dumper;

my @array=(41,7,2,3,4,6,1,10);

#lets assume we want 2 indexes from the above array 

#which will add up to sum 10

my $sum = 10;

my ($idx1, $idx2); # these are the indexes

my $i = 0;

#convert the array into hash with keys starting from 0 and

#array elements stored as values

my %my_hash = map {$i++ => $_}@array;


print Dumper \%my_hash;

# create a reverse hash to retrieve keys from values    

my %rhash = reverse %my_hash;

#iterate through the first hash, we need to make sure the 

#hash is sorted so that the hash keys match with array index order

for my $key (sort keys %my_hash) {

    #this is to store the second value which adds 

    #to first value $my_hash{$key} to be equal to sum

    my $second_val = $sum-$my_hash{$key};

    #if the second key exists in reverse hash, we 

    #can easily find the index

    if (defined $rhash{$second_val}) {

        $idx1= $key;

        $idx2= $rhash{$second_val};

        print "Indexes are $idx1 $idx2\n";

      }

   }