Two Sum Algorithm in Python
Learn how to solve the classic Two Sum algorithm in Python! An incredibly fun tutorial on using Hash Maps to upgrade your code from slow O(n^2) to blazing fast O(n).
Try it yourself
Run this code directly in your browser. Click "Open in full editor" to experiment further.
Click Run to see output
Or press Ctrl + Enter
How it works
The Two Sum problem is the ultimate rite-of-passage for anyone learning algorithms! It's one of the most famous coding interview questions in the world.
The Goal: You have a list of numbers and a target number. Find the two numbers in the list that add up exactly to the target!
Two Ways to Solve It
1. The Brute Force Way (Slow & Steady)
The absolute easiest way to solve this is to just check every single possible pair!
You take the first number, and add it to every other number to see if it matches. Then you take the second number... and so on.
2. The Hash Map Way (Lightning Fast!)
What if we only had to look at each number exactly once?!
We can do this using a Hash Map (which is just a standard Python Dictionary).
1. As you look at a number (say, 2), you ask: "What complement do I need to reach our target of 9?" (Answer: 7).
2. You check your dictionary: "Have I seen a 7 yet?"
3. If no, you just toss the 2 into your dictionary's memory and keep walking down the list.
4. When you eventually get to the 7, it will calculate its complement (2), check the dictionary, see that you already safely logged the 2, and boom! You found the pair instantly!
The Magic Keyword: Space-Time Tradeoff
By using just a little bit of extra memory (O(n) space for our dictionary), we mathematically sped up our program from O(n^2) time all the way down to O(n) time. This concept is called a Space-Time Tradeoff, and it's the absolute secret to unlocking almost every advanced algorithm!
