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\$
8
  • 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\$ Jun 2, 2016 at 12:43
  • \$\begingroup\$ @OlzhasZhumabek I thought of that, but std::sort is O(NlogN) while this is O(N) \$\endgroup\$
    – Dean
    Jun 2, 2016 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\$ Jun 2, 2016 at 12:48
  • \$\begingroup\$ I should try then, no requirements on the size of the vector. \$\endgroup\$
    – Dean
    Jun 2, 2016 at 13:33
  • 1
    \$\begingroup\$ @SergeyA lookup on a hash map should be O(1) on correct sizing of the buckets. \$\endgroup\$ Jun 4, 2016 at 10:25

1 Answer 1

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\$
2
  • \$\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, 2016 at 15:32
  • \$\begingroup\$ @Dean sorry, fixed, removed the [i] \$\endgroup\$
    – coyotte508
    Jun 2, 2016 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.