3
\$\begingroup\$

I'm solving some online puzzles and I had this problem:

Given a vector, write code to find the indices of TWO values which sum to a given number N

so if I'm given [2, 5, 6] and N = 8, I should output the 0-based indices [0, 2].

I wrote the following code to do this in O(N)

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_multimap<int, int> numbers_multimap;
    numbers_multimap.reserve(nums.size());
    for(size_t i = 0; i < nums.size(); ++i) {
        numbers_multimap.emplace(nums[i], i);
        auto interval = numbers_multimap.equal_range(target - nums[i]);
        for (auto it = interval.first; it != interval.second; ++it) {
            int other_position = it->second;
            if (other_position != i)
                return vector<int>{i, other_position};
        }
    }
    return vector<int>{};
}

and it works, but I noticed that there are faster solutions.

Since I suppose the algorithm is already quite fast, I'd like to know if there are additional pro tips to improve the runtime of this code.

\$\endgroup\$
  • 1
    \$\begingroup\$ I think it would be better to sort vector, start from the beginning and search N - nums[i] using binary search. What is maximum size of the vector? \$\endgroup\$ – Incomputable Jun 2 '16 at 12:43
  • \$\begingroup\$ @OlzhasZhumabek I thought of that, but std::sort is O(NlogN) while this is O(N) \$\endgroup\$ – Dean Jun 2 '16 at 12:44
  • 1
    \$\begingroup\$ have you benchmarked it? big O is algorithmic complexity, but things as memory aliasing, cache consistency can throw that complexity in trash bin \$\endgroup\$ – Incomputable Jun 2 '16 at 12:48
  • \$\begingroup\$ I should try then, no requirements on the size of the vector. \$\endgroup\$ – Dean Jun 2 '16 at 13:33
  • 1
    \$\begingroup\$ @SergeyA lookup on a hash map should be O(1) on correct sizing of the buckets. \$\endgroup\$ – Andrew Lazarus Jun 4 '16 at 10:25
1
\$\begingroup\$

You can emplace after testing for the complementary, it simplifies the code and avoids using a multimap:

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> numbers;
    //removed because can be very inefficient if nums is big or there are a lot of duplicates
    //numbers.reserve(nums.size());

    //a micro optimization could be to loop from the back and compare
    // i to 0 in the test but it doesn't weigh much against container operations
    for(size_t i = 0; i < nums.size(); ++i) {
        int num = nums[i];
        if (num > target) {
            continue; //no need to waste time storing it either, assuming all numbers are unsigned
        }

        auto it = numbers.find(target - num);
        if (it != numbers.end()) {
           return {i, it->second};
        }
        //no need to emplace for integers? actually slower than insert if key is already present
        numbers.insert({num, i});
    }
    return {};
}

If the values are in a range comparable to the size of the vector, you can just create a valarray<int> of size maxValue+1, fill it to -1 on initialization, and use that instead of the map to check if a value is already present.

Another small optimization that can be done would be to have your loop like that:

int i = 0;
for (int num : nums) {
    //...
    //calls to 'continue' can be replaced by goto endloop

endloop:  
    i++; //equivalent in performance to ++i for basic types
}

Iterating over the container like this (which is actually moving a pointer forward) is faster than accessing the element of the vector by its index every time. Although it's a relatively small optimization given that there are map operations used in the loop itself.

\$\endgroup\$
  • \$\begingroup\$ I don't think I can loop this way: for (int num : nums[i]), an integer has no begin function \$\endgroup\$ – Dean Jun 2 '16 at 15:32
  • \$\begingroup\$ @Dean sorry, fixed, removed the [i] \$\endgroup\$ – coyotte508 Jun 2 '16 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.