Two Sum Problem is one of the most common problem you would want to solve if you are preparing yourself for interviews. Heres how I solved this problem in 3 different approaches using C++

Two Sum Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Approach 1: Brute Force

The brute force approach is simple. Loop through each element x and find if there is another value that equals to target - x.

vector<int> twoSum(vector<int>& nums, int target) {
    int len = nums.size();
    for(int i = 0; i < len; i++) {
        for(int j = i + 1; j < len; j++) {
            if(nums[j] == target - nums[i])
                return { i, j };
        }
    }
    return {-1, -1};
};

Complexity Analysis

  • Time complexity : O(n^2). For each element, we try to find its complement by looping through the rest of array which takes O(n) time. Therefore, the time complexity is O(n^2).
  • Space complexity : O(1).

Approach 2: Two pointer

To implement this techniques array should be sorted then point front to begging of the array & rear to end of the array. Loop through array until front less than rear. Sum up array[front] + array[rear] and check if it matches to target we are looking for.

vector<int> twoSum(vector<int>& nums, int target) {
    int front = 0, rear = nums.size() - 1;
    sort(nums.begin(), nums.end());
    while(front < rear) {
      int sum = nums[front] + nums[rear];
      if (sum == target)
       break;
      else if (sum > target)
       rear--;
      else
       front++;
    }
    return {front, rear};
};

Complexity Analysis:

  • Time complexity : O(nlog(n)). sort function takes nlog(n) time.
  • Space complexity : O(1).

Approach 3: Hash Table

Extra memory needed for this approach. While we iterate and inserting elements into the table, we also look back to check if current element's complement already exists in the table. If it exists, we have found a solution and return immediately.

vector<int> twoSum(vector<int>& nums, int target) {
      map<int, int> map;
      vector<int> pairs;
      for(int i = 0; i < nums.size(); i++) {
          int complement = target - nums[i];
          if(map.find(complement) != map.end()) {
              pairs.push_back(map.find(complement)->second);
              pairs.push_back(i);
              break;
          }
          map.insert(pair<int, int>(nums[i], i));
      }
      return pairs;
};

Complexity Analysis:

  • Time complexity : O(n). We traverse the list containing n elements only once. Each look up in the table costs only O(1) time.
  • Space complexity : O(n). The extra space required depends on the number of items stored in the hash table, which stores at most n elements.