Two Sum
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Given a list of numbers and a target, find the positions of the two numbers that add up to the target.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1For one number, what exact value would you need as its partner?
- Hint 2Searching the whole list for that partner every time is slow. Where could you keep the numbers you already passed so the check is instant?
- Hint 3A dictionary (hash map) answers "is this value there?" in one step. Store each passed number with its position.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
You have a ₹900 gift card and must pick exactly two items that use it fully. You walk down the shelves with a small notebook. Holding a ₹200 item you do not compare it with every shelf again: you only ask "did I write a ₹700 item in my notebook?". If yes, done. If not, write ₹200 in the notebook and walk on.
- The obvious way
Pick every number and look through all the others for its partner. With 100,000 numbers that is billions of checks (O(n²)).
- The key insight
For the number in your hand the partner is fixed: target minus that number. If you wrote down every earlier number in a notebook, "is the partner there?" is a single look. One walk through the list is enough, because a pair is found when the second of the two arrives.
- The algorithm
- Start with an empty notebook (a dictionary: number -> position).
- Take the next number and work out its partner: target minus the number.
- Look the partner up in the notebook. Found? Answer = its saved position and the current position.
- Not found? Write the current number and its position in the notebook and move on.
Watch it run
Examplenumbers = [2, 7, 11, 15], target = 9
Take 2. To make 9 we need 7. The notebook is empty, so no. Write down: 2 is at position 0.
{2: position 0}Where people slip
- Write the number in the notebook AFTER checking, otherwise one number can pair with itself.
- Duplicates are fine: [3, 3] with target 6 works because the first 3 is saved before the second is checked.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def two_sum(nums, target):
seen = {} # number -> position
for position, number in enumerate(nums):
partner = target - number
if partner in seen: # we met the partner earlier
return [seen[partner], position]
seen[number] = position # write it in the notebook
return []Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.