Interview Prep #3: Two Sum

#career #beginners #cpp #interview

Problem

We are given an array of integers and another a target integer. We'd like to find the indices of two numbers in that array such that the sum of these integers add up to the target. We cannot use the same number in the array twice and there is exactly one solution. This problem is on leetcode.

Example

input:[2, 7, 11, 15], target = 9,
output: [0, 1]

Solution

The first thing that came to my mind is to sort the arrays. But sorting would not work because as soon as we sort the array we change the original indices of the array.

The correct solution involves the use of hash maps. We iterate over the array and store the number in a map along with the index. We also check in the map if we can find a pair for the current number to get the sum to the target.
If we can, we return the current index along with the index of the complement number from the hash map. This takes linear time complexity ie. O(n)

pair<int, int> find_sum(vector<int>& nums, int target) {
  map<int, int> m;
  for (auto i = 0; i < nums.size(); ++i) {
    int c = target - nums[i];
    if (m.find(c) != m.end()) {
      // pair found
      return {m[c], i};
    }
    m.insert({nums[i], i});
  }
  // If we cannot find a pair
  return {-1, -1};
}