LeetCode 1 – Two Sum

Posted on December 21, 2013

Last updated on July 30, 2014

Solution to the LeetCode Two Sum problem.

There is a number of ways to do this:

• Naive – explore all pairs of two – $$O(n^2)$$
• Sort and use two pointers – $$O(n\log{n})$$
• Use a hashmap – $$O(n)$$, but requires some extra bookkeeping.

In this solution, I’ll use a hashmap, since I’ll use the sorting method for the later questions on Three-Sum and Four-Sum. The hashmap solution works as follows – add all the elements one by one to the hashmap. Then, traverse the array again, and for each element $$i$$, check if $$c-i$$ (where $$c$$ is the desired sum) is in the hashmap. If so, we found a match. The issue is we need to keep track of the indices where each element appeared at, otherwise we’ll get false positives for cases such as $$[5,2]$$ and we are looking for a sum $$10$$. The algorithm will say a solution exists, when it clearly doesn’t.

Markdown SHA1: 1ac32aca7559364e9b263c06da60918259478568