3
\$\begingroup\$
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int size = nums.size();
        vector<int> toRet;
        unordered_map<int,pair<int,int>> myMap;
        for(int i = 0; i < size; ++i){
            myMap.emplace(nums[i],make_pair(nums[i],i));
        }
        for(int i = 0; i < size; ++i){
            int toFind = target - nums[i];
            if(myMap[toFind].first == toFind && myMap[toFind].second != i){
                toRet.push_back(i);
                toRet.push_back(myMap[toFind].second);
                return toRet;
            }
        }
        return toRet;
    }
};

How do I make this run faster? I can't think of anything. Right now, it is slower than 47% of submissions. Could you please provide some hints?

\$\endgroup\$
2
  • \$\begingroup\$ What is "2 sum"? Please describe the problem you are trying to solve. \$\endgroup\$
    – G. Sliepen
    Sep 4, 2022 at 7:39
  • 2
    \$\begingroup\$ @G.Sliepen It's the k-sum problem, where k=2. \$\endgroup\$ Sep 4, 2022 at 7:57

1 Answer 1

4
\$\begingroup\$

It's possible to solve this in a single pass:

  • Use a map<int, int> to store values you've seen so far, and their first index, let's call it seen
  • For each value, let's call it current:
    • Is target - current in seen?
      • If yes, return the pair of the index in the map and the current index
      • If not, and current is not yet in seen, then put current into seen and the current index
  • If you reached the end of the collection without returning, then there is no such pair that sum to target.

This algorithm should be faster than the posted code, because:

  • it works in a single pass
  • uses less memory (unordered_map<int,pair<int,int>> replaced with unordered_map<int, int>)
  • uses fewer conditions
\$\endgroup\$
2
  • \$\begingroup\$ Thank you so much for the clear explanation. I have one more question though. Even after doing so, 20% of submissions had lesser runtime. Is there an even faster algorithm than this? \$\endgroup\$ Sep 5, 2022 at 21:06
  • \$\begingroup\$ I can't think of a faster algorithm. The implementation of the algorithm is important too. If you post your implementation as a follow-up question, you may get tips to speed it up further. Keep in mind that the performance metrics of programming challenge websites are usually not very precise. If your submission is in the bottom 10% then it would be good to understand why and improve it, but when it's already in the top 20%, I think that's good enough, and it's not worth pushing it further. I definitely don't recommend micro-optimizations that sacrifice readability. \$\endgroup\$
    – janos
    Sep 6, 2022 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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