Two Sum

Problem

Analysis

The brute force way would be to check every two digits from the given list. This would be a O(n^2) solution which is not very useful. The other option I thought of was to sort the array first. Unfortunately, for the given problem sorting would accomplish nothing. Is there a way to solve this in O(n) time? Perhaps, if we could trade some extra space for time.

EDIT: sorting is actually useful! Have a look at Two Sum II.

First Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
      /* keep track of numbers that we have
         encountered already from the input vector
      */
      unordered_set<int> set;
      vector<int> ans;
      for (int e: nums) {
        int remainder = target - e;
        /* if remainder already exists in our set then we are done */
        if (set.find(remainder) != set.end()) {
          ans.push_back(e);
          ans.push_back(remainder);
          break;
        }
        set.insert(remainder);
        set.insert(e);
      }
      return ans;
    }
};

The first attempt failed. I failed to read the complete requirement. The question is asking for a list of indices 🙄. And the other problem with this solution is that we are inserting remainder as well. This is wrong 🙀!!! We end up inserting numbers into the set that don’t even exist in the input.

Accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
      /* keep track of numbers that we have
         encountered already from the input vector
      */
      unordered_map<int, int> m; // nums value --> nums index
      vector<int> ans;
      for (int i = 0; i < nums.size(); i++) {
        int remainder = target - nums[i];
        /* if remainder already exists in our map then we are done */
        if (m.find(remainder) != m.end()) {
          ans.push_back(i);
          ans.push_back(m[remainder]);
          break;
        }
        m.insert({nums[i], i});
      }

      sort(ans.begin(), ans.end());
      return ans;
    }
};

Lesson learned

Please read the question more carefully!!!