Skip to content
Two Sum LeetCode Optimized C++ solution

Two Sum LeetCode Optimized

The Two Sum problem from LeetCode. Given an array of numbers and a target number and we should return the indices of the two numbers that sum up to the target. Let our target be 7 and then if our array contains 3,4 and 3+4=7 we will return the index of 3 and 4.

Examples

Input: nums = [4,3,2,4], target = 5
Output: [1,2]

Input: nums = [2,2], target = 4
Output: [0,1]

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Solution Explanation

As said in the question, there is only one possibility or combination and we can simply use two loops and try to add all combinations but it will take a long time. This can also be done in a single iteration but to do that we need to keep track of the previous elements and their positions too, as we were asked to return their index not the numbers.

Input: nums = [2,7,11,15], target = 9
  • Take an unordered map to store previous data
  • We are using the map as it is convenient to store both the number and its index position
  • Start iterating from start to end of the array size

Now in the loop,

  • Take diff=target – a[i],
  • Suppose target = 9 and a[i] =2 we get diff= 9-2=7
  • This way if we find 7 next time it’s easier for us to solve
  • Now check if 7 is present in the map, it isn’t
  • Now add {2,0} to the unordered map and continue the loop

Loop continues,

  • Next, we get diff=9-a[i] => 9-7 = 2
  • Now check for 2 in the map and yes it’s present
  • return previous[2] i.e returns it’s position 0 and
  • the present (i) i.e the position of 7

Code for Two Sum LeetCode – C++

Link to practice Two Sum LeetCode Problem

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
                unordered_map<int, int> prevMap;
         for (int i = 0; i < nums.size(); i++) {
            int diff = target - nums[i];
            if(prevMap.count(diff))
                return { prevMap[diff], i };
            prevMap[nums[i]] = i;
     }
//return something, however the answer is guarenteed above
           return {};
    }
};

Conclusion

This post is part of my #30DaysChallenge to write a blog post every day on what I learn. When I first tried to solve this Two Sum problem, I did use two loops but then I found this method saves a lot of time, What do you say?

Tags: