Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Shell

The actual problem

Algorithms may feel very rigid and math-y, but they aren’t. To solve the problem you want to get the “gist” of the problem, not a perfectly defined discreet way of conceiving it. You should not try to make your brain into a computer to work with a computer.

The “gist” of the problem

In human language: find a way to observe two elements in a list of elements which form a target sum

The simplest answer

Compare every combination of integers based on index. Or, in natural language, walk the list and try every possible pair.

Polynomial time.

A faster solution

The above requires us to “walk” the array twice (polynomial time). But we can also just transform the array in sub-polynomial time (with quick or merge sort) then walk it once. How much better is this in reality? Well better is relative to our goals. Let’s be critical thinkers and examine what the difference between n^2 and n * log(n) looks like and when we should be concerned about it.

For an array of size 500 the difference is substantial 500^2 vs. 500 * 500log(500) + 500 | 250,000 vs. 5,000 operations (so let’s hand wave and say 30-50 clock cycles per operation). If the size of the data is going to scale past say 100 integers in which case there is a roughly 9000 operation difference, or be performed frequently, then we probably don’t want a polynomial time solution.

How much difference does 9000 operations make in a modern computing environment? Well… that’s harder to answer. It probably doesn’t matter a lot of the time. If you can constrain the input to below about 100 and you’re not implementing library code that needs to cover the most generic cases possible, finding something better for a simple operation like this is almost pointless. You’ll find out if you need optimization and you can come back and identify key points where it’s needed. Throwing every data structure at every possible problem the first time you encounter it is is not good engineering practice.

But we’re interviewing… so let’s assume we’re writing library code and we want the optimization.

Ok, so sort the list then traverse. I’ll be deeply offended if I’m asked to recall merge or quick sort from memory during an interview, so let’s just use the standard library.

Ok nice. In an actual interview I’d hang up right here. But since I’m practicing, I should really stretch my brain. As we discussed above, n * log(n) + n is pretty good if we need it, but n is a lot better. Let’s push the boundaries a bit. I’m sure we can find an n solution. What’s more, there’s a lot to algorithms. Knowing your standard libraries, knowing how to think up test cases to poke at little mistakes you’ll almost certainly make, but also… really learning algorithms in the way you need to to pass interviews is (and maybe helpful for thinking about computing in general) is really about recognizing the pattern underlying the problem.

Once you know the pattern underlying the problem and you know how to solve it, you can apply it across all different problems you’ll find in interviews. You should be able to recognize it quickly, strip the pomp and frill, and maybe only need a small amount of extra tactical code surrounding the core strategy to pass.

What’s the “core” of this problem? Remember the “gist” I outlined above? Traversing a list of integers to find… well let’s leave it there. Strategies for traversal. Maybe we want two integers that add up to a sum. Maybe we want the two greatest integers in the list. Maybe we have a magic function we need to plug integers in a range into to determine if they equal a sum and really we’re still just traversing a range of integers to find a value. The “core” of this problem, traversing a list of integers, and the strategies for doing so, is what you want to focus on, as it will apply to many problems.

In Search of One Pass Answer

Right off the bat the impulse to traverse the list from either end is obvious. We know there is an answer (it was part of the question), so we can just walk towards the middle from either end to get there… right?

No there’s an issue with this. While stepping towards the middle when we progress one of our indices we’re cutting off an entire chain of possibilities for testing the possible combinations of elements. In plain language we’re “walking past” many potential solutions on the way towards the middle. But that doesn’t mean there isn’t a way to do it.

Ok I’m not going to lie, I gave up thinking there was a solution to this, because you can construe a view of the problem such that it’s unsolvable (you can’t “walk” all combinations of the array in linear time). But I was wrong to think that means there is no linear time solution. You can use a hash map to construct a linear time solution to this problem. I found this very clever implementation in the comment section of Leetcode.

Would I do / expect this in an interview? Probably not. Most of the time I wouldn’t even attempt going this far. It’s very clever though, props to whoever came up with it. But what is important to me in this case is that I ingest this pattern as a hint to consider in future cases…

Next time I think I have an unsurpassable constraint involving a polynomial time traversal, or I notice myself “walking past” solutions in my mind, maybe I can store info I need in a map and use a linear traversal…

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> pair;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < nums.size(); j++) {
                if ((nums.at(i) + nums.at(j) == target) && i != j) {
                    pair.push_back(i);
                    pair.push_back(j);
                    return pair;
                }
            }
        }

        return pair;
    }
};

#include <algorithm>

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> pair;
        vector<int> copy(nums);
        std::sort(nums.begin(), nums.end());
        int i = 0;
        int j = nums.size() - 1;
        while (i < j) {
            if (nums.at(i) + nums.at(j) < target) {
                i++;
            } else if (nums.at(i) + nums.at(j) > target) {
                j--;
            } else {
                int originalI = find(copy, nums.at(i), true);
                int originalJ = find(copy, nums.at(j), false);
                pair.push_back(originalI);
                pair.push_back(originalJ);
                break;
            }
        }

        return pair;
    }

    int find(vector<int>& nums, int val, bool forward) {
        if (forward) {
            for (int i = 0; i < nums.size(); i++) {
                if (nums.at(i) == val) {
                    return i;
                }
            }
        } else {
            for (int i = nums.size() - 1; i >= 0; i--) {
                if (nums.at(i) == val) {
                    return i;
                }
            }
        }
        return -1;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];
            if (map.find(complement) != map.end()) {
                return { map[complement], i };
            }
            map[nums[i]] = i;
        }
        return {-1, -1}; // or return {};
    }
};