I have signed up to leetcode. The first problem I did was called “Two Sum”, where you need to find two numbers in an array that when added together match a target number. I thought I’d write some notes here to remind myself about the details in the future.
Brute force solution
So, the most obvious solution is comparing all combinations of each two numbers with two nested for loops. This is easy to code and simple but doesn’t scale well as it is O(n²).
Hash map solution
The next easiest solution for me was to store the numbers in a hash map (in c++ std::unordered_map<>) and use that to find the required complement of each number. This is the most scalable solution as it has O(n) time complexity but also has O(n) space complexity.
Ordered list iterating solution
The solution that didn’t come as easily to me as it probably should have was an algorithm to pass through the numbers in a linear way if they are already sorted. I intuitively knew this was possible but it didn’t come to me until I drew out an example of the numbers on a whiteboard:
Once written down like this, it becomes clear that we can iterate from the start and end of the array heading towards the centre while comparing values. If the sum of the values is bigger than target then we decrement j. If the sum is smaller than target then we increment i. If i and j cross then we don’t have a match.
By the way, I think some of the leetcode test case arrays are not sorted. If we sort the array first then we have an O(n log n) solution, which in theory should not be as fast as the hash map solution. However I found that this was in fact quicker than the hash map solution. I guess the leetcode test cases must be small and possibly mostly sorted. I don’t think there is UI in leetcode to check the submission test cases, so I don’t know for sure.
So the moral of the story is to write out an example even if it is simple.
I have since found this google interview example video that is a nice walkthrough of this problem: