clueless coding // TODO: be smarter

LeetCode 1. Two Sum: Explanation and C++ Solution

Problem Statement


Given an integer array of size N, 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.

Function Signature:
  C++
    vector<int> twoSum(vector<int> input, int target) {...}

Inputs:
  input = [2, 4, 6, 7]
  target = 9,

Outputs:
  [0, 3]
     (because input[0] + input[3] = 2 + 7 = 9)



Solution #1 (suboptimal): Nested Searching

O(N2) runtime, O(1) memory


The most obvious solution to this problem is a simple search: we simply look at each element in the input, and compare it with every other element until we find a combination that works. Essentially, we check every possible combination made up of two elements until we find the right one.

In the example above, this would involve evaluating combinations as follows:

input = [2, 4, 6, 7]
target = 9

2 ->
2 + 4 // == 6, fails
2 + 6 // == 8, fails
2 + 7 // == 9, found an answer
4 ->
4 + 2
4 + 6
4 + 7
...

Of course, as soon as we find an answer, we stop - we know that there is only one solution (the problem spec said so!), and that we’ve found it. This approach gives us our solution, is easy to digest, and is relatively easy to code up:

vector<int> twoSum(vector<int> input, int target) {
  // double loop to create every combination
  for (int i = 0; i < input.size(); i++) {
    for (int j = i + 1; j < input.size(); j++) {
      // return the current combination, IF it works
      if (input[i] + input[j] == target) {
      vector<int> result = { i, j };
      return result;
      }
      // it didn't work, keep trying
    }
  }
}

O(N2) runtime - the outer loop runs N times. The inner loop, when i == 0, runs N-1 times. When i == N, the inner loop runs 0 times.

Then, we’re running our code (0 + 1 + 2 + 3 …. + N-1) times, which we can approximate as the summation N(N-1) / 2 => (N2-N) / 2. For simplicity, we can express this as O(N2) complexity.

We can also think of this as looking at each unique pair in the set, which is an N2 problem.

O(1) memory - we aren’t storing anything of significance.



Solution #2 (optimal, using memory): Hashing

O(N) run time, O(N) memory


Instead of checking for EVERY possible combination, we can frame the problem a little bit differently. For every element, we’re really just looking for its complement.

For example, if our target is 9 and we’re looking at a 2, we want to know if there’s a 7 in the input. If we were looking at a 4, all we need to know is whether or not there’s a 5 present elsewhere in the input.

In the last approach, we satisfied that need by individually looking at every single element and checking for it. Unfortunately, that approach is a little wasteful - we’re constantly looking at elements that we’ve already seen in the last iteration.

We can eliminate this waste by utilizing a hashing approach - essentially, we’ll store information that we’ve already processed. Instead of saying ‘let’s go check for a 4’, we’ll say ‘do I remember seeing a 4 earlier?’

In people logic, that would look something like this:

input = [2, 4, 6, 7]
target = 9

2 ->
looking for an 7 - have we seen one? nope!
remember that we saw a 2 at position 0
4 ->
looking for a 5 - have we seen one? nope!
remember that we saw a 4 at position 1
6->
looking for a 3 - have we seen one? nope!
remember that we saw a 6 at position 2
7 ->
looking for a 2 - have we seen one? YES!
where was the 2 that we saw earlier? at position 0
where are we now? at posiition 3

All of a sudden, we don’t have that slow, gross O(N2) approach - we’re only looking at every element once! It turns out implementing logic like this is extraordinarily easy if we use a hashtable, like so:

vector<int> twoSum(vector<int> input, int target) {
  unordered_map<int, int> map; // our 'memory'
  for (int i = 0; i < input.size(); i++) {
    int complement = target - input[i];
    // if we haven't seen the complement yet, remember
    if (!map[complement]) {
      map[complement] = i;
    }
    // we've seen it! use what we remember!
    else {
      vector<int> result = { i, map[complement] }
      return result;
    }
  }  
}

O(N) runtime - we only operate on each element once.

O(N) memory - in the worst case, we have to store a piece information for every single element in the input - this is the tradeoff that we pay for reducing our runtime complexity.